3 ms·
> > cons-cell is a terrible abstraction on modern hardware > Could you expand on this? Sure, that one is pretty easy. cons cells are effectively 2 pointers.
by bsder 13y ago
> > cons-cell is a terrible abstraction on modern hardware
> Could you expand on this?
Sure, that one is pretty easy. cons cells are effectively 2 pointers. Consequently, they are not guaranteed nor expected to be near one another in memory.
Now, that's not a big deal with respect to the first pointer. That contains the thing, so we always have to chase that down.
In a Lisp/Scheme cons-cell list, the second pointer needs to be referenced to get to the next cons cell. So, we have to chase a second pointer just to move to the next element.
Every time you chase a non-contiguous pointer like this, the processor may have to bring in a cache line and that's a big penalty.
Contrast this to say, an array/vector. To get to the next element you just add some small amount to the current index. It's likely already in the same cache line as the previous element.
Arrays/vectors have a big win over pointer-based lists in terms of locality of reference on a modern microprocessor.
There is a second problem with cons cells in that their abstraction in terms of the language also has problems:
"Programing Language: Why Lisp Do Not Have a Generic Copy-List Function"
http://xahlee.info/UnixResource_dir/writ/lisp_equal_copy_list.html http://xahlee.info/UnixResource_dir/writ/lisp_equal_copy_lis...
http://www.nhplace.com/kent/PS/EQUAL.html http://www.nhplace.com/kent/PS/EQUAL.html