Re: Gradual Growth of Memory Use?
"Yuri Davidovsky (as work at disclosure dot ie)" <[email protected]>
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
> On 13 Mar 2025, at 14:05, Anthony REY <[email protected]> wrote: > > Not a Lisp expert at all : but I was wondering if accessing data in a cons cell chain is similar to accessing data in a LinkedList, which is O(N) ? Yes, cons chains dbm is talking about are the linked lists you mentioned. Essentially each element in it is a pointer to a heap location and a pointer to the next cons element. You are essentially making two memory lookups for every single element traversed which can be bad news for performance if you have to do that continuously with huge lists. > Yuri's answers made me wonder if you might be running into heap fragmentation and then constantly cache miss when accessing the data pointed by your cells ? Yes, the lack of spacial locality is a big problem for cache efficiency and linked lists are probably the worst offenders when it comes to that, although I would imagine there may be ways to mitigate it somewhat, for example by using continuous arrays of pointers behind the scenes which will save the time on looking up the next cell. > I don´t know enough about Garbage Collection or LispWorks to give more than an hazardous hypothesis, but I do work in the video games industry and we developed some strategies and data structures to make sure that the memory is staying contiguous in memory to please the cache as much as possible and ensure we can reach our real time performance goals Game developers are quite known for being the top of the industry when it comes to memory management, I am not surprised that you are surprised to see how things are done in other areas. _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html