[gambit-list] List vs vector in Gambit Q
Adam
adam.mlmb at gmail.com
Sun Nov 29 05:57:28 EST 2020
Hi Brad!
On Thu, 15 Oct 2020 at 03:11, Bradley Lucier <lucier at math.purdue.edu> wrote:
> On 9/30/20 9:26 AM, Adam wrote:
> > Dear Marc,
> >
> > Is it that Gambit tends to allocate a list's elements, in sequential
> > memory order, and |cdr| internally tends to be a +1 pointer operation?
>
> If you have a (list arg1 ... argn) then yes, I believe that gsc
> generates code to allocate the pairs in the list adjacently in memory.
>
At allocation time they will tend to be in sequential memory, yes, I share
your understanding on this one.
I also believe a GC will tend to keep a chain of cells essentially in
sequence also.
I would be curious to learn if Gambit implements any particular special
tricks to "help" locality - I thiiink Marc mentioned something to this
effect in the past but I don't remember. Something about that a |cdr| call
reduces to a memory address + operation.
> I recall you said something to this effect in the past.
> >
> > Thought came to mind now, that what about that Gambit could have use of
> > an |apply| form that takes a vector as argument, due to prevalence of
> > speed benefit of vector over list.
> >
> > Please share your thoughts on this one.
>
> I don't see how this would work, each pair in a list is still allocated
> using three words (one for the tag, one for the car, one for the cdr).
>
What I meant was a form (apply-vector thunk vector), such that
(apply-vector + '#(1 2 3)) leads to (+ 1 2 3).
While |apply-vector| would admittedly be a nuance less lispy than |apply|,
then it would have certain performance benefits, e.g. space density of a
vector is higher than that of a list.
Since this kind of form would need to be implemented in Gambit's runtime,
it's quite lowlevel, I wanted to bring it up with Marc directly here on the
ML"
I added it as a feature request in a GitHub issue now:
https://github.com/gambit/gambit/issues/644
Adam
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20201129/d570e45f/attachment.htm>
More information about the Gambit-list
mailing list