I am sorry Dave, I am afraid I cannot do that

In previous Xbox discussions, it came up that the failure rate for consumer electronics is 1-2%. Assume it is 1% for a while, then consider the following.

Intel is shipping CPUs which support trusted execution. A part of this technology is the TPM chip sitting on your motherboard. The idea is that trusted software will use bulk encryption keys to encrypt application data. But then where are these keys stored? The idea is to use the TPM chip to associate a particular encryption key with the identity of the software, and then have the TPM chip encrypt the bulk encryption key. Only the protected software will be allowed to use the TPM encryption services it is supposed to because all TPM encryption keys remain protected inside the TPM.

Only of course, 1% of such devices will fail to do what they're supposed to no matter what, regardless of the reason. So, let's see... I run a protected environment to keep my data safe, and 1 in 100 TPM modules will eventually fail to do their work? Even if it is 1 in 1 million, there are plenty of PCs to go around so that such failures will show up.

So your TPM fails. Or your motherboard is fried, or whatever else. Then what? Well, do you remember your data? Good, because you will have to recreate it from scratch. In other words, you are pretty much screwed. Russian roulette, 21st century style.

By the way, since TPM keys do not leave the TPM chip, how do you transfer encrypted application information to other computers? In particular, how do you backup your own computer in case it blows up taking with it the TPM module used to encrypt your valuable data?

And of course, suppose you are provided a workaround for all that --- such as trusted I/O, etc. Do you see the amount of damage this can do in the hands of the wrong people, unless there is a back door for law enforcement which means the whole TPM exercise is worthless anyway? It's not like motivated adversaries will not find the back door without telling anybody, you know?

Finally, there are these things called implementation bugs... AACS thought they had it nailed down but they are not very happy people these days, are they?

So all of this just does not work for consumers because they would want to store their own data, and by doing so they would be putting it at unnecessary risk. Might as well keep the key in your head, use a variant of RSA on a computer running a serious OS without an internet connection, and be done with it.

If we remove user data from the equation, however, we have much stronger DRM in the case where data is provided to us such as movies, music, and so on. This is something that consumers do not want either.

Oh well... I am not buying or using anything related to that. If that means no movies for me, then so be it. Not only it will not be much of a change anyway --- I have plenty to do just writing my book in the first place.

Quote of the day for today

"Victories avoid and hide deficiencies"

Eduardo Gonçalves de Andrade, Tostão

Request for hash functions

The book is going well, and the draft just got to 347 pages. Since I am writing about hash, I will be reviewing the hash functions listed below. Do you know of any other functions worth mentioning? Perhaps you even wrote one of your own! If so, please let me know. Thanks!

Updated list:

• Arash Partow's hash
• Bit xor funnel
• Bob Jenkins' 32 bit hash
• Bob Jenkins' bit mixing hash
• C++ library extensions hash
  
• Daniel J. Bernstein's hash
• Donald E. Knuth's hash
• ELF hash
• Fowler, Noll and Vo's hash (FNV)
• Herbert Glarner's HSH 11/13
• Kernighan and Ritchie's hash
• Modulo hash
• Java's hash for strings
  
• Justin Sobel's hash
• Paul Hsieh's hash
  
• Peter J. Weinberger's hash
• Robert Sedgwick's hash
• SBDM hash
• Simple bit shift hash
• Simple sum hash
• Squeak's hash for strings
• Zobrist hash
  

AnnotatedMethod>>hash, part 3

After some changes, I saw the rest of the problem. The hash in CompiledCode, called via super from AnnotatedMethod, only scans the first literal (if any) to calculate the hash value.

However, a significant amount of AnnotatedMethods have the same first literal, and thus the collision rate was still about 3k hash values to 3.6k objects with rather large chi^2 values. Refining hash in AnnotatedMethod to scan the rest of the literals as well addresses this issue, and now the Hash Analysis Tool returns lovely values:

• Collision rate: 1.005017
• Chi^2: 0.010538
• Avg chi^2 mod P: 0.500917
  

Hold on though, having hash scan every literal in an annotated method might mean hashing largish literals sometimes! It could be that doing more work in hash takes more time than the savings due to less collisions, particularly because the new hashes for sequenceable collections in general use every object to derive the hash value.

Ok, so let's check it out. The test case is to put all annotated methods in a set.

• Scanning the first literal only: 68 ms/iteration.
• Scanning every literal without using primitives: 60 ms/iteration.
  

So really, doing more hash work pays off by 10% or so. Also... of those 60 ms/iteration spent doing asSet scanning all literals without primitives, about 72% of the execution time will be replaced by work done in the VM when the primitives are available to the image. So far, so good.

But what is the performance of this test in a verbatim VW image, which will not scan every object in sequenceable collections when calculating hash values? Well, my dev image has 3.6k annotated methods, and the verbatim image has only 2.4k annotated methods. So, adjusting the amount of annotated methods to 2.4k in the dev image, we see that:

• the verbatim image takes 35ms/iteration regardless of which AnnotatedMethod>>hash (improved or not improved) is used.
• the dev image with all its improved hashes (Strings, Symbols, ByteArrays, LargeIntegers, and SequenceableCollections) takes between 27 and 40ms/iteration, depending on which 2.4k annotated methods are selected from the 3.6k available. Also, about 72% of the execution time (which includes the time it takes for primitives to fail) will be replaced by work done in primitives as shown by the TimeProfiler.
  

Even taking the most conservative numbers, 40ms/iteration of which 72% will be replaced by VM work should squarely beat 35ms/iteration.

But what is the real impact of primitives? I was so curious I couldn't help checking it out. So I just tried loading my dev image with the new primitiveful VM for the very first time. I am so happy about this --- the image just started up and is working fine!

Well, of course... if all primitive failure code matches the behavior of the VM, then why shouldn't it work? :)...

So I checked the same test cases again. Indeed... with all its hashes running in primitive mode now, the dev image goes through the test case in anywhere between 17.8 and 21.7ms/iteration. This is close to 2x faster than the verbatim image, even at the cost of generating much better quality hash values.

Looks like a win to me!

Hash Analysis Tool 1.8 available!

Datasets were moved to a separate package, Hash Analysis Tool Datasets. Enjoy!

Plane crashes into building: 200+ dead

Here is a snippet from CNN's report:

[CNN's reporter said that t]he airport is notorious for having short, slippery runways [and that t]he runway was recently resurfaced but the cutting of grooves to channel rainwater off the pavement had not been completed [...].

A Brazilian court in February banned large jets at the busy airport because of safety concerns, The Associated Press reported. But an appeals court overruled the ban, saying it would hurt business and that the safety problems did not warrant halting air traffic, according to AP.

"When you fly into Congonhas airport, it is like you are literally flying past people's living rooms in apartment blocks," Hennigan [a reporter from The Times of London] said. "Then you land on the runway. It is completely surrounded by the central part of Sao Paulo city. This is not an airport out on the edge of the city. This is right in the city."

Really... so we have short, slippery runways that will not drain water properly, and an airport surrounded by city. What is the weather like at Sao Paulo's airport right now, I am afraid to ask. Why, of course --- rain!!!

See what I mean? "Oh, it would hurt business to actually play it safe, so screw it because we want money more than we want people alive".

Of course maybe the accident had nothing to do with the combination of factors mentioned above, and certainly the investigation has not had a chance to run its course. However, this news article is damning. A plane skidded yesterday too, because of rain. During this year, another 4 planes had skidded in a similar manner. The one today finally managed to crash and burn. The list of other issues which remain broken with Brazil's air transportation is breathtaking.

This situation seems so familiar... it so much irritates me when we put stupid colorful papers in front of people, e.g.:

• Strong hurricanes will never go through New Orleans. Ever. So keep building on sinking ground and eroding the protective marshlands anyway.
• For years, a fatal issue with the 737 rudder was not addressed although there was significant evidence that indicated the problem did exist --- including four plane crashes in which everybody died. Many funny things happened, including the convenient vanishing of critical defective parts taken from planes. Boeing even sued the government alleging its air traffic controllers failed to steer the plane away from wind conditions that simply do not exist.
  
• Oh, it's foam, see? It's been like that for over 50 flights and nothing fatal happened before. No issue here, just cross your fingers as usual and let Columbia land.
  
• According to a report by the Union of Concerned Scientists, two thirds of nuclear reactor pressure vessels in the US are susceptible to catastrophic failure of the nozzles that keep control rods in their place. Nozzle failure could lead to a loss of coolant accident. So, when this problem became apparent, did we immediately do what other countries started doing, i.e.: inspect and fix reactor vessels? Well, the answer seemed to be that shutting down the reactors to perform repairs was cost prohibitive. Since we were not shutting down the reactors, we just skipped the inspections altogether. Until, of course, 10 years later we found cracks here as well. Also found: a football sized cavity in a reactor vessel head. The China Syndrome all over again.
  

When we do that kind of garbage, we put ourselves into a position from which we will bet, by means of our arrogant decisions, that our will is more powerful than reality. Sometimes I wonder how much money some people think they need to pile on a volcano about to erupt so that they can safely sit over the whole thing without being promptly carbonized as soon as the explosion goes off.

In short, the Universe does not give a rat's tail about our illusion of being clairvoyant, rich, or even significant.

And oh by the way, for the bad things that actually happened in the list above, I am not aware of anybody going to jail for manslaughter. I can go to jail if I unwillingly kill somebody while driving my car, but it seems to me that none of the above are something that would justify time in a cell in our lovely society because it could be argued the wrongdoings were done in the pursuit of profit and happiness.

We just suck.

PS: Did you know air traffic controllers in the US typically have work schedules that make it impossible for them to sleep anything close to 8 hours a day? Did you know that at one airport the air traffic controller left planes unattended for 18 minutes because he really had to go to the bathroom --- and that at the particular airport there was only one controller to begin with? I am sure you feel safe now after you go past the see-you-naked security machine.

AnnotatedMethod>>hash, part 2

So I ran the new hash of AnnotatedMethods through the Hash Analysis Tool, and it promptly reported 3k hash values to 3.9k objects. At first I thought it wasn't that bad because the collision rate was ~1.3. This was a good improvement already, so I was happy. Then, I looked at the chi squared values.

Now, good chi squared values are typically under 1, and ideally the first one should be either zero or almost zero. For the sake of illustration, the new hash for symbols produces chi square values along the lines of 0.00001 and 0.39.

In the case of AnnotatedMethod, both chi squared values were over 19. Something like that is really bad because it means there are very large spikes in the distribution of hash value occurrences. This translates into the existence of largish families of objects which have the same hash, and this is exactly what brings performance of hashed collections to a crawl.

But this measurement was done in my dev image which already had all the new, more proper hashes for strings, symbols, byte arrays, large integers, and that in addition has 28 bit identity hash values as well*! How was this possible?

I examined the calculations of the hash analysis tool, and selected a hash bucket with multiple annotated methods. The methods were different, yet they had the same hash. I started digging, and eventually found myself debugging this most innocent looking expression.

#(#menu) hash

If you take a look at what happens, you will see what is going on. The realization made me think about reimplementing SequenceableCollection>>hash to be some sort of bitXor: funnel, e.g.:

^self
inject: self size hashMultiply
into: [:answer :each | answer bitXor: each hash]

Although more analysis is needed, at this point I cannot help feeling leaving things as they are is tantamount to tempting fate and causing hashed collections to have subpar performance in the general case.

This argument could just be wrong. Therefore, changing the hash of sequenceable collections requires serious consideration in the first place. But, fortunately, some of that heavy thinking has already been done. For example, when hashing strings (a particular kind of sequenceable collection), evidence suggests that to produce a good quality hash in the absence of any prior knowledge of what kind of strings will be hashed, the calculations must use all available characters. Thus, it appears that the same conclusion is inescapable in this case as well.

Thoughts?

*The 14 bit hash values are upscaled to 28 bits so that hashed collections do not have to guess whether a hash value is an identity hash value indeed, or just a low hash value instead. Further upscaling does not seem to be necessary for a 32 bit image because in such images indexed collections have a maximum size of 2^28 slots. Rough measurements show this results in a small performance increase for hashed collections because hashed collections now have to do less work. It also addresses some pathological cases such as the performance of (1 to: 1 million) asSet.

Hash Analysis Tool 1.7 available!

This new release holds on to less memory after results are calculated, remembers results from previous runs for each data set, and adds more data sets.

Enjoy!

Regarding AnnotatedMethod>>hash

Travis found some issues with AnnotatedMethod>>hash and made reference to the hash work I am doing.

While in this case it wasn't absolutely necessary to provide a hash method because it was still compatible with the rule that says a = b => a hash = b hash, nevertheless, as Travis mentions, it would have been strongly preferable to do so because performance was rather bad.

Interestingly indeed, the = method was not very efficient either. After a bit of work, it runs 3x faster:

= aMethod
"Use the fact that the vast majority of annotated methods have only 1 attribute message"

| receiverAttributes argumentAttributes |
super = aMethod ifFalse: [^false].
receiverAttributes := self attributeMessages.
argumentAttributes := aMethod attributeMessages.
argumentAttributes size = receiverAttributes size ifFalse: [^false].
argumentAttributes size = 1 ifTrue: [^(argumentAttributes at: 1) = (receiverAttributes at: 1)].
^argumentAttributes allSatisfy: [:any | receiverAttributes includes: any]

Based on that work, the hash I chose to implement is as follows.

hash

| receiverAttributes |
receiverAttributes := self attributeMessages.
receiverAttributes size = 1 ifTrue: [^(receiverAttributes at: 1) hash bitXor: super hash].
^receiverAttributes hash bitXor: super hash

Although it's better than what was there before, this still causes a collision rate of 2.8k hash values to 3.9k objects... it could use what I am still working on :). Hopefully this helps in the mean time!

PS: if anybody else has hash pet peeves, please please let me know. This would be an ideal time to get them addressed.

C after Smalltalk

The feeling is quite strange. After becoming proficient in assembler, I was shown Smalltalk in 1996. I haven't looked back into assembler or C or Pascal since then. And now, I find myself writing primitives in C. I have to say that, after using Smalltalk so much, I find that writing code in assemblish-C is fun.

But how is that possible? Writing asm was fun 11 years ago, but after learning Smalltalk I still don't have such a high opinion of what I used to do back then! And yet, it is fun indeed. What's even exciting about it is that in the same way one can write C in Smalltalk making a mess more often than not, I see that one can write Smalltalk in C with convincingly nice results in the majority of cases.

In other words, I see that 11 years of Smalltalk have taught me how to write what I'd describe as beautiful C.

Ok fine, convincingly nice results such as what? Well, a primitive hash prototype in front of me can crunch data at a blistering 160mb/sec in modern yet modest machines --- and I can't help feeling the code is as readable as a Smalltalk method!

More to come...

Speedup for 32 bit VW GemStone clients

One of the things I noticed at a GemStone project is that sometimes the access to GemStone data becomes slow. The reason why it happens in this particular case is that the client image will keep a dictionary that maps between local and remote objects, and that the dictionary is based on identityHash. Now, for 32 bit VisualWorks images, identityHash is 14 bits long. So this means that if there are a lot of objects mapped back and forth, then there will be significant collisions, and thus linear search in the gbx hash buckets of the dictionary will take its time. If my memory serves me right, this approach has been replaced by something else for the 64 bit GemStone (and there are 20 identityHash bits in 64 bit VW) so this is not a long term issue, but if you still see this problem in 32 bit images then you can try the following.

There is a primitive referenced in WeakArray, number 422, which is invoked by the four argument message indexOf:replaceWith:startingAt:stoppingAt. This primitive replaces the identical occurrence of an object with another one in the receiver given the index bounds provided to the primitive.

The primitive works on any array like objects, so you could copy it to the gbx hash bucket class and thus replace the linear search done in Smalltalk with a primitive. But, you say, this primitive replaces objects instead of just searching for them. However, note that you can use it to search if you provide the same object as arguments to indexOf: and replaceWith:, at negligible extra cost compared to having a primitive that does not replace.

Preliminary work by GemStone suggests this is a valid approach, and barring any unforeseen issues this improvement will be in the next release of GBS. I hope this helps!