[Python-ideas] Associative arrays in hardware

Neil Toronto ntoronto at cs.byu.edu
Wed Apr 16 08:47:45 CEST 2008


Mathias Panzenböck wrote:
> However, there still could be a collision so you have to compare the key 
> by value anyway, so the performance might not by that much better. And 
> pythons strings are immutable so the hash code is cached anyway and has 
> not be calculated every time. But this instruction could only calculate 
> a hash of a sequence of bytes (like a string), not of a complex object 
> which has some fields that form the key (and ohters that dont). So it's 
> pretty useless in my opinion. (But I'm so tired I can hardly think, 
> maybe I'm missing something.)

Yes, and that's that most language identifiers are "interned" strings: 
just a pointer to them is sufficient for equality comparison. (Ruby and 
every Lisp dialect on the planet call these "symbols".) Python is so 
very close to using nothing but interned strings for all namespace dicts 
that it wouldn't be that difficult to change it.

It's entirely possible that a hash of the string pointer would be 
sufficient, so it wouldn't even be necessary to hash the string and send 
it along.

> Neil Toronto schrieb:
>> Full-on associative memory wouldn't be necessary. If there were a 
>> machine-level instruction in current chips that did a dict-style 
>> lookup almost as fast as a base+index*size, Python could *scream*. It 
>> might work like 80x86's lea (load effective address):
>>
>>      hashaddr   base, recsize, dictsize, value, destreg
>>
>> It would be very CISCy, and there are a whole host of practical 
>> problems dealing with hashing functions, good collision resolution, 
>> etc. But any pointer/index-based (e.g. interned string) lookup could 
>> go almost as fast as C++'s "this->". Mainstream is moving toward 
>> dynamic languages, and it makes sense to support that in hardware.
>>
>> Heck, I hear routers and switches already have things like this. Does 
>> anybody have the ear of an Intel chip designer?
>>
>> Neil
> 




More information about the Python-ideas mailing list