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