On Monday 21 of February 2011 19:58:32 you wrote:
> in recent IRC discussions, the old requests (demands) for array support
> in PicoLisp rose their ugly heads again.
> I'm a bit disappointed about that, as it (or, better, its absence) is a
> central issue, and it shows that I couldn't make clear at all what
> PicoLisp is about.
> So I felt I should try to explain my view more clearly, and wrote a
> little article in the wiki. It is a bit too short, perhaps, and perhaps
> even increases the confusion :(
> But nevertheless, I posted it. It might be improved in the future, and
> can be found under
> Articles & Essays -> Array Abstinence
> or at the direct link "http://picolisp.com/5000/-2-1d.html".
The article lays it out all clearly and neatly, with one caveat I'd like to
<rant mode on>
Alex writes, ``Given a number, the associated data can be found [in array] in
That holds true if, and only if, the relevant part of the array is already
present in L1 cache. Otherwise, about 200...300 CPU cycles  will be wasted
waiting for the cache to be filled before data is available to the CPU. This
wasted time actually dominates the execution time, in pathological cases.
The data will be in cache most of the time for small arrays, but will NOT be
in cache for larger arrays. So if you think ``for large ammouts of data arrays
will be significantly faster'', don't -- there's significant overhead related
cache loads. To the contrary, traversing PicoLisp's linked list will be quite
Now if you access the array in a semi-random order, so-called `cache trashing'
will ensue. Pretty much like reading random data from the harddrive (for
example from swap). The CPU, starved of data, will idle uselessly.
On the other hand, if you access the array it sequentially, it's not better
than simply traversing the PicoLisp linked list. You can even reasonably
expect the CPU to pre-fetch relevant data into the cache.
If you really, positively, want to index a huge number of data, use a binary
search tree with complexity of O(log n) on average. Building BSTs from
PicoLisp lists is easy :)
</rant mode off>
To wrap it up: surprisingly, due to modern memory/CPU speed disparity, random
access to data in an array isn't all that fast. Theoretically O(1), but in
practice it will incur high overhead of cache misses.
Traversing a list is fast enough unless you have huge datasets. In that case,
use a binary search tree.
(& some other publication by some Sun guy)
``One can't proceed from the informal to the formal by formal means.''