Knee surgery

As an anonymous person pointed out, the knee in the curve is an illusion. Here is the same chart displayed with varying scales for the x and y axes:

You can see that the position of the “knee” depends upon the scale of the X and Y axes.

The whole chart is a problem. Not only does it show a knee, but the rest of the chart has the data all squished up along either the X or Y axis. It is going to be hard to compare different charts if they all look like this. I want the whole chart to be scale invariant.

(Can you guess where this is going?)

The curved line in the chart represents the solution to x × y = 6100000. This line appears to come pretty close to the actual garbage collection count when you use MIT/GNU Scheme to compile itself. Since the product is a constant, we have a hyperbolic curve. To transform this into something more reasonable, we want to take the logarithm of the curve in both the X and Y direction. This will change our line from x × y = constant to x + y = constant (because logarithms transform multiplication into addition).

This chart is certainly more interesting! First, notice how the measured garbage collection counts fall in almost a straight line. The curve that approximates the count is a straight line, and you can see that the actual garbage collection count deviates from this line slightly at the ends. Second, notice that the lines 10 × x, x, and x/10 become parallel. This is convenient, too. Finally, notice that the knee is gone. This sort of chart won't fool us with a fake knee.

Now that we have something of an interesting baseline, it would be instructive to plot other processes that generate garbage and see how they look. (upcoming post)

A bit of a problem

Once again, here is a plot of the actual garbage collection counts as a function of heap size:

and we mention that we want to be “beyond the knee” in the curve. So where is that “knee”?

The green line is the plot of f(x) = 6100000/x, or, to put it another way, the plot of x × y = 6100000. The knee in the curve ought to be where x = y = √6100000 ≈ 2470. But look at the chart! Just by eyeballing it, we can see that 2470 is nowhere near what anyone would call the knee.

More on GC

I had been thinking of improving the garbage collector in MIT/GNU Scheme. I carefully measured the current GC performance so I could quantify any improvements. This uncovered a bug (see earlier post), but it also uncovered something more interesting. Here is a plot of the number of garbage collections as a function of heap size for the problem of compiling all the Scheme code in MIT/GNU Scheme:

This graph looks an awful lot like the graph of minimal collections. In fact, if we plot the minimum number of garbage collections necessary for about 6100000 blocks, we get this:

That appears to be a really good fit. This isn't too surprising, because a GC that collects only when it is almost out of memory ought not to be doing much more work than the minimum necessary.

What makes this interesting is this: We can clearly see the “knee” of the curve, and we have enough memory to be “well beyond the knee” when we compile all of Scheme. This means that the total number of garbage collections will be quite low. If the garbage collector is fast enough, the total GC time will also be quite low. For example, when given 40000 blocks of memory, MIT/GNU Scheme will compile itself in about 3 minutes of which only 2.6 seconds total are spent in garbage collection. And as I noted previously, with sufficient memory, there need not be any garbage collection at all.

Notice that the details of the collector are unimportant. MIT/GNU Scheme uses a variation of the Minsky-Fenichel-Yochelson-Cheney-Arnborg algorithm, but it could just as easily use a mark-sweep collector. The point is that when you are only doing a few dozen collections, it doesn't matter much what algorithm you use because changing the algorithm will make little impact on the total run time. (Suppose I had the world's greatest garbage collector that just blows away the current one. Then I could reduce the total time from 182.6 seconds to exactly 180 seconds. This is less than a 5% improvement and not worth pursuing.) (A reference count GC, however, would be a problem because it traces garbage rather than live storage.)

So my original plan is pointless. There is no advantage to improving the garbage collector if it doesn't take more than a small amount of time, and it looks like you can achieve this by simply throwing memory at the process. So long as you have sufficient memory, you can make the cost of a collection be close to (or even equal to) zero.

At least it looks that way...

Thoughts about GC

Suppose I have a program that, when run, allocates a total of 10 GiB (10×2³⁰ bytes). If it happens that I have more than 10 GiB of heap, then I don't need to worry about running out. If my heap is smaller than 10 GiB, I'm going to have a problem.

It is often possible to re-use storage by overwriting the previously written information. If the result computed by a program (including the side effects as part of the ‘result’) is completely invariant with respect to the value of a location in memory, then that memory location could be re-used. Depending upon the program and the runtime system, re-use can be the responsibility of the programmer, or there can be an automatic means of storage management (e.g. a garbage collector). Regardless of how re-usable storage is identified and made available to the program, we can use the pigeonhole principle to determine the minimum number of times that we must re-use some part of memory. For example, if my program uses 10×2³⁰ and I have 10×2³⁰−1 bytes of heap, then at least one byte somewhere will have to be re-used.

So let us suppose that our program which allocates 10 GiB is to be run with a 2 GiB heap and our runtime system provides a garbage collector so we don't have to manage our storage manually. Suppose further that our garbage collector is not continuous, but has some sort of identifiable ‘cycle’ during which it locates re-usable memory. On each cycle the garbage collector can reclaim at most 2 GiB, so we know the runtime system must perform a minimum of at least five garbage collection cycles. It may perform many, many more than five, but it cannot perform fewer because it would have to recycle more than 100% of the heap at some point.

Another way to state this is that the number of garbage collections times the size of the heap must be equal to or greater than the total amount of storage allocated by a program. Here is a graph that shows the minimum number of collections needed for a program that allocates 50 bytes of storage.

The discrete jumps in the graph are because we aren't considering partial allocations (less than 1 byte). When working with realistic heap sizes, we can approximate this graph by dividing the total allocation by the heap size. The green line in this chart plots 50/x.

More to come...

Measuring GC times

MIT/GNU Scheme has a command line parameter, --heap, that allows one to specify the size of heap in 1024 word blocks. On a 32-bit machine, the heap size is limited because MIT/GNU Scheme stores the type tag in the upper bits of the word. On a 64-bit machine the word size is wider, so it is possible to specify extremely large heaps without worrying that the address will overflow into the type tag.

For kicks, I decided to vary the value of the heap size and see what effect that had on the task of MIT/GNU Scheme compiling itself.

Heap	GC Count	Cumulative GC Time in ms
6000	1056	25800
8192 (64 MiB)	764	19120
10000	623	17910
16384 (128 MiB)	377	10980
32768 (256 MiB)	188	7350
50000	124	5560
65536 (512 MiB)	94	5000
100000	63	4410
131072 (1 GiB)	48	3910
150000	42	4160
200000	32	3800
250000	26	3560
262144 (2 GiB)	25	3050
300000	22	3360
350000	19	3260
393216 (3 GiB)	18	2740

Collecting this data was tedious, so I spent a fair amount of time thinking about a model that could explain the results. At first glance, everything looks about right: the more memory, the fewer GCs and the less total time is spent garbage collecting. The problem is that the curve predicted by my model doesn't fit the empirical data at all. Of course this means that my model is either wrong or incomplete.

I have since figured out the problem, but I thought I'd let people puzzle over it themselves for a bit, first.

50 years ago — April 28, 1961

This is an excerpt from the forth coming LISP 1.5 Programmer's Manual.

Provision is made in LISP 1.5 for allocating blocks of storage for data. The data may consist of list structure or data words. Arrays may have up to three indicies.

To declare an array, us the function array. Its argument is a list of arrays to be declared. Each one must be for list structure or non-list structure.

Suppose ALPHA is to be a 10 x 10 array of list structure and BETA a 5 x 5 x 5 array of non-list structure. The array function is

ARRAY ((
     (ALPHA (10,10) LIST)
     (BETA (5,5,5) NONLIST)    ))

To find the value of B_3,4,2: (BETA 3,4,2) or (BETA I J K) with a pair list.

To set ALPHA_3,4 to "YES": (ALPHA (QUOTE SET) (QUOTE YES) 3 4)

Array uses marginal indexing for maximum speed. The total number of words used by an array whose size is D₁ x D₂ x D₃ is 4 + D₁ + D₁D₂ + D₁D₂D₃. If the array is 2 dimensional, D₁ = 1. If the array is 1 dimensional, D₁ and D₂ = 1.

To save space, specify the dimensions in increasing order.

ALPHA (3,4,5) takes less words than ALPHA (5,3,4).

Compatability of LISP 1 and LISP 1.5.

1. EVALQUOTE has two arguments while APPLY has three. To change a LISP 1 program for LISP 1.5 simply eliminate the p-list if it is null. If the p-list is needed, then the function apply is available in LISP 1.5,
2. Arithmetic in LISP 1.5 is new, improved, and generally incompatible with LISP 1.
3. LISP 1.5 has many extra features. There [sic, these] are being written up for the new LISP 1 Programmer's Manual. Until it comes, check in Room 26-265.

— Michael Levin

Artificial Intelligence Project

RLE and MIT Computation Center Memo 24

Arithmetic in Lisp 1.5

Fun with scammers

No Scheme or Lisp content today. I was amusing myself for a while with this email exchange. The strings of digits are courtesy www.random.org. I even found a site that creates fake Western Union receipts.

---

Hello,

I'm writing this with tears in my eyes,my family and I came down here to Edinburgh Scotland for a short vacation unfortunately we were mugged at the park of the hotel where we stayed,all cash,credit card and cell were all stolen from us but luckily for us we still have our passports with us.

We've been to the embassy and the Police here but they're not helping issues at all and our flight leaves in few hrs from now but we're having problems settling the hotel bills and the hotel manager won't let us leave until we settle the bills the amount needed now is just $2,700..I am so confused right now and thank God i wasn't injured because I complied immediately. Waiting to hear from you. Robert

I sent this message to Bob's other account:


I just got this message that supposedly came from you. It is plausible enough that your friends might fall for it! You should email your friends and assure them that you are OK and to NOT SEND MONEY
~jrm

Thanks for checking on me, well the message is from me and not a hoax. I'm presently stuck in UK and really in a bad situation.....I have been talking to the lazy embassy but it's taking them time process me help, and it's hard to get hold of a phone, that was why I had to send out email for help....I need a financial help with getting back home...all i need is $2,700.,but anything you could assist with now be helpful ..let me if can you have the money wire to me through western union

Thanks. 

Robert

I'm glad to hear your email is ok, it would be terrible to be mugged and hacked. Where do you need it sent?
~jrm

 Glad you replied back. I am full of panic now and the police only asked me to write a statement about the incident and directed me to the embassy,i have spoken to the Consulate here but they are not responding to the matter effectively,I really need your help to get myself out of this place. Well all i need now is just $2,700 but any amount you can afford will be appreciated, you can have it wired to my name via Western Union i'll have to show my passport as ID to pick it up here and i promise to pay you back as soon as i get back home.

 Here's the info you need at western union location below

 Name: Robert G 

Address: 48 Princes Street, Edinburgh, Scotland 

 Kindly email me the transfer details as soon as you have it done.Please let me know if you are heading out to western union now. 

Thanks

Robert

 What's going on?

 I was only able to wire $300 (I hit the limit on my ATM). I can send a lot more tomorrow, but will you have time to get it?
 ~jrm

 Please Let me have the western union confirmation number # M.T.C.N, so i can be able to pick up the Money. I'm freaked out at the moment please keep me posted. 

 Robert. 

 Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

 Thanks for your effort,Let me have the western union confirmation number # M.T.C.N. Awaiting for your reply. 

 Robert 

I left him dangling on this one.

 What's going on? 

 Robert . 

 My apologies, Robert, (I know you are in trouble, but I do have to sleep at times!) The MTCN is 2665592734

HOWEVER!!! IMPORTANT!!!!

I didn't want to broadcast that over email because it could be read by someone unscrupulous. So I added in your wife's birth date. Just subtract that out to get the real tracking number. I hope you can figure that out. Please let me know. If you want, I have an additional $500 I can send right away.

 What's going on,I just got back from Western Union and i was told there was no record for the transaction,kindly check the receipt and get back to me with the correct confirmation # 

 Awaiting to reply. 

 Robert .

 Trip number 1.  I'm shocked it didn't work.

What?! Did you remember to subtract your wife's birth date from the number I gave you?

 Omg!! I am full of panic now,Let me have the scanned receipt For Payment giving to you by the Western Union Agent.

Uh oh.  I'm busted... maybe I can vamp a bit....

How can I do that? You know I don't have a scanner. I've got an idea! What's the phone number of the hotel that is giving you problems? I'll call the manager myself and put it on my credit card.

No reply.  I was going to give up but it occurred to me to check for an on-line receipt generator (they have everything on line, don't they?) They do.  I sent him a nice receipt.

 Good news! I found a scanner. Please let me know if everything is ok.

 Thanks for your help.. i just got the money but there seems to be a problem with the conversion rate, i noticed the money came out here in $300but all i need is $2,700 as i requested, don't know that the conversion is that low, please i will need your further assistance so i will be needing $2,400. Please let me know when you will be heading out to western union. Waiting to read from you.

Hmm, he read the receipt, but didn't make a Western Union run.  I'll string him along a bit.

 I'll have to go by the bank (again) to get an additional check. I should be able to do that after work, in a few hours. Hang in there! I'm very worried.

 Ok,I will be waiting ,Do e-mail the full Western Union Transfer Details once you have it done. 

 Keep me posted.

 Robert.

I'm trying to get the guy to go `off script'.

 URGENT
 Robert, I need to know if you want the money in US Dollars, GB Pounds, or Euros, and what the exchange rate is. Can you get back to me as soon as you can? I'm really sorry about this, hope you are surviving.

No reply.  Better dangle some cash.

 I sent some more money. Did you get it? Is everything all right?

 OK...Can i have the full transfer details (MTCN) so i will be able to pick up the money. Waiting to read from you. 

 Thanks Robert.

 The MTCN is 4677254413 Please let me know when you get it!

 Are you there? 

 Robert, did you receive the money? Are you still in trouble? Is there anything more I can do?

 Let me have the confirmation details # M.T.C.N. Awaiting for your urgent reply. Robert 

 Please do get back to me with the Western Union Control Number M.T.C.N# Please Keep me posted. 

 Robert 

 This guy just has a one-track mind.  It seems impossible to get him `off script'.

Robert,
What is going on? Are you all right?

 I just checked with Western Union and they say you haven't picked up either of the two wires that I sent! Are you having difficulty getting them?

 The Western Union Control Number M.T.C.N # are these:
 2665591653 --- amount $300
 3207519347 --- amount $500

 Please let me know if you have any problems retrieving the money.
 ~jrm

 Are you kidding me or what,cause i was told at western union office the money you sent to me was not there. Please Let me know what's going on am freaked out here. 

 Robert.

 Yes!  Trip number 2.  He's probably figured out I'm playing him, though.  Let's goad him into one more trip.  A bit of an insane rant to allay his suspicions and we'll sweeten the pot just a bit more...

I don't know what to say, Robert. Perhaps they have a different system in Edinburgh and the numbers don't match? Are you sure that you are telling them the right numbers and didn't get them mixed up?

 I checked with Western Union, and the agent told me that the money was there and that you didn't pick it up. Why don't you go to the Royal Bank of Scotland? They are at 4 Princess Street, right around the corner from where you are staying. They should be able to straighten this out right away.

 I'm surprised you suggest that I am kidding. Why would I be so cruel? I have $800 on the line, and I'm doing this for your benefit. I'm not the victim here, you are. Do you think I would wire you this kind of money and then make a joke about it? Do you think I get a kick out of imagining you walk back and forth to Western Union for no reason? This is a bad situation and you seem to think I'm making it worse! I'm not sure you are taking this as seriously as I am. Are you sure you didn't get injured?

 I'm going to try this one more time, and I expect action on your part. I have wired an additional $200 dollars for a total of One Thousand ($1000) dollars. I really cannot afford any more, so I hope this is enough. The details are these: 

Sender: Joseph Marshall
 Receiver: Robert G, 48 Princess Street, Edinburgh Scotland
 Amount: $1000.00 (One Thousand) 
Money Transfer Control Number: 1822631749
 Transfer Fee: 50.00
 Number: 10341731365

 And I am enclosing a receipt. Please be sure to get these details correct. I am awaiting to hear that you have collected the cash.
 ~jrm

The receipt was fake and I included a “security question”: Who's your daddy? I was sure this would tip my hand, but....

 Robert, it has been 7 hours since I sent this. Did you get it?
 ~jrm

No i didn't,I will like to go back to western union and make this complain to them that all the confirmation number they give you was invalid ok..

YES!  Three trips!  Well, that's good enough for me.