Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Wed, Sep 20, 2023 at 1:32 PM Stefan Monnier via Emacs development
discussions. <emacs-devel@gnu.org> wrote:
> >> Re your last change in [0], why use records directly instead of having
> >> the code being generated via cl-defstruct?  The commit messages doesn't
> >> really explain your reasoning to me.
> > The library is supposed to provide alloc/free functions that run in
> > O(1) time to the extent that is possible for emacs-lisp code, for use
> > in process sentinels and similar situations.  I took a look at the
> > byte-code generated for those two functions when using the
> > cl-defstruct definitions, and the accessors and setters were
> > not inlined.
>
> That's odd.  Could you give more details about what&how you checked that?

For your reference, I reset the main branch of the github repo to the
last cl-defstruct version and put the subsequent commits on branch
'feature/no-cl-lib'.
I've attached the output of M-x disassemble for tam-free after
byte-compiling each version.  Excluding the tam-already-free error
condition, the feature/no-cl-lib version contains only stack
operations, constants, aref, aset, branches, and a single return.  On
an admittedly cursory inspection of bytecode.c, none of those
operations do any consing, and there will be no calls to maybe_gc
because the unconditional jumps are all forward.

You're correct, the accessors and setfs _are_ inlined as arefs and
asets.  I mistook the initial call to tam--table-get-slot to be an
accessor.  There are a lot of type-of, all of which are excessive for
this type of low-level function.  tam--slot structs should only appear
in tam--table and tam--pool structs and the slots vectors of those
should contain only tam--slot structs.  There are no public functions
that return a slot or set an entry in a slots vector of a tam--table
or tam--pool.  In any case, every call operation invokes maybe_gc
unconditionally, so there is a chance of a GC occuring during the
execution of the byte-vector.

>
> > Aside from the unknown complexity of invoking those functions, every
> > call has a risk of overflowing the current stack and requiring an
> > additional stack segment be allocated.
>
> That would still be O(1) in my book.

Is that actually guaranteed?  I haven't looked to see if obtaining an
additional stack segment might cause a gc or just a system call to get
more memory.

> > Accumulating a list in the right order is only O(n^2) if you only keep
> > the head of the list.  The queue structure (or what I would write with
> > let-bound variables) holds a reference to the last cons cell of the
> > list to use in adding an entry on the end.  It's probably negligible
> > for very short lists, but it's just bad form.
>
> Using `push`es followed by `nreverse` is usually more efficient than
> either of those.  It's a standard idiom in Lisp for good reasons.
> If you care about the constant of your O(1) above, I recommend you use
> `nreverse` here as well :-)

I am now recalling this discussion.  I suppose it does just transpose
the setcdr operations into a separate (but much faster) loop
implemented in C with much lower loop overhead.

I only care about the allocate, free, claim, and release functions
providing O(1) performance.  A list is getting consed in the
"free-list" and "live-list" reporting functions, after all.

Thanks for taking the time to look it over.

Lynn

disassembled-cl-defstruct-tam-free.txt
Description: Text document

disassembled-no-cl-lib-tam-free.txt
Description: Text document