3 ms·
It has nothing to do with pointers, but memory access patterns can have a huge performance impact. Iterate over a large array, and do the same over a large link
by ygra 12y ago
It has nothing to do with pointers, but memory access patterns can have a huge performance impact. Iterate over a large array, and do the same over a large linked list. The latter cannot make use of the CPU cache in any meaningful way, for example.
- alkonaut 12y agoAnd the linked list can share storage between different lists which the straight array cannot. There are always benefits and drawbacks with different structures. "list" doesn't say what data structure is used, it only describes the semantics (an ordered collection of items). It's the same with a vector.
- nickik 12y agoI agree, memory access patterns can have a huge performacne impact. The cache is importent but its not as simple as you think. Im not gone explain to you why it work, but see paper [1]. Its not about the clojure vector, but basiclly the same and he explains performance and he it is quite fast for lookup. Adding is also quite fast, both for immutable and the mutable case. [1] http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf