[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