Re: GETF Speedup?

> Anyway, the lesson is: if you need fast key access, use lists, as strange as it sounds, just make sure they are built in a single sitting. 

Interesting point!

But wouldn’t you expect Lists to be fast in Lisp? That is its primal data structure. 

I half expect that lists are, as often as possible, not actually stored as conventional linked lists. But rather, as a serial vector with tags indicating something about the CAR/CDR relationship.

I haven’t examined the implementation used by SBCL or CCL, nor do I fully understand what I’m seeing in a LW DISASSEMBLE. But I have heard of something called CDR-Coding.



> On Oct 11, 2025, at 08:17, Yuri Davidovsky (as work at disclosure dot ie) <[email protected]> wrote:
> 
> 
> 
>> On 11 Oct 2025, at 16:29, David McClain <[email protected]> wrote:
>> 
>> So doing a “proper” test would be a bit more involved. I’d guess you build the list, stash it away, run a compile or two against some external Lisp source, then come back and query the speed of list traversal.
>> 
>> But then, after the first failed scan, the entire table would be back in cache again, and every subsequent query would win again...
> 
> I would not consider it a failed test, in fact I would make sure that as much stuff as possible IS located in the cache before the test. That is exactly what cache is for in the first place, to optimise the memory access. Ironically, in a situation where you build lists quickly, when the conses can be laid out sequentially in the cache, lists indeed should be faster than hash tables, whose memory allocation is more sparse and the key hashing is needed for each lookup. 
> 
> But in a situation where you build up lists slowly (like you were doing in your measurement app before migrating to resizable vectors), and you have one cons here, and another cons there, there indeed lists may be slower as they will have poor spatial locality in the memory. 
> 
> Anyway, the lesson is: if you need fast key access, use lists, as strange as it sounds, just make sure they are built in a single sitting. 
> 
> _______________________________________________
> Lisp Hug - the mailing list for LispWorks users
> [email protected]
> http://www.lispworks.com/support/lisp-hug.html


_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html