[Python-ideas] Associative arrays in hardware

[Neil Toronto]

Greg Ewing wrote:
> Neil Toronto wrote:
>> 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,
> 
> But how would you make it that fast without some kind of
> associative lookup hardware?

Good point. They'd have to add that to the RAM. :D Or at least the cache...

> Without that, you'd just be implementing the Python dict
> lookup algorithm in microcode, which might be a bit
> faster, but not spectacularly so -- the same number of
> memory accesses would still be needed.

Right, it's memory access that's the bottleneck. A hardware dict lookup 
could know its own memory access characteristics and plan for them. In 
particular, it would be much better at predicting what to bring into 
cache next than current CPUs are at predicting based on software 
algorithms, if they predict at all. On the other side of it, they could 
optimize their lookups for their own hardware, particularly collision 
resolution methods.

Neil