Hi list,

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 
mention.

<rant mode on>
Alex writes, ``Given a number, the associated data can be found [in array] in 
O(1) time.'' 

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 [1] 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 
to 
cache loads. To the contrary, traversing PicoLisp's linked list will be quite 
fast.

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.


[1] http://lwn.net/Articles/252125/
(& some other publication by some Sun guy)

-- 
dexen deVries


``One can't proceed from the informal to the formal by formal means.''
-- 
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to