[GNU ELPA] New package: tam

[GNU ELPA] New package: tam

[Lynn Winebarger]

I'd like to submit "tam" (table allocation manager) for inclusion in
GNU ELPA.  The source is available at
https://github.com/owinebar/emacs-table-allocation-manager

tam provides functions to track the (manual) allocation of a fixed
number of resources to specific objects.  All the data structures of
the table are fixed at initialization, so that adding or removing a
particular object should not provoke a garbage collection in any
obvious way.  The allocation and deallocation are meant for use in
process sentinels and the like.

I have previously implemented some of the functionality of this
package in a package async-job-queue on MELPA.  However, since that
work cannot be assigned to the FSF, I am writing a more general
purpose async job scheduler from scratch.  In particular, the
scheduler will provide a facility for users to set a maximum number of
async processes to run simultaneously, then manage the assignment of
those process slots to jobs.  The tam functions provide a generic way
to manage that resource allocation in process sentinels.  tam.el was
created on September 15, 2023.

;;; tam.el --- Manage use of slots in a fixed size table  -*-
lexical-binding: t; -*-
;;; Commentary:

;; Table Allocation Manager
;; Provides an interface to managing the usage of the slots in a fixed size
;; table.  All allocation is done during initialization to avoid triggering
;; garbage collection during allocation/free operations.

;;  API:
;;
;;  (tam-create-table N) => table of size N
;;  (tam-table-fullp TABLE) => nil unless TABLE is full
;;  (tam-table-emptyp TABLE) => nil unless TABLE is empty
;;  (tam-table-size TABLE) => number of slots in TABLE
;;  (tam-table-used TABLE) => number of slots of TABLE in use
;;  (tam-table-get TABLE IDX) => contents of TABLE slot at index IDX
;;  (tam-allocate TABLE OBJ) =>
;;      if not full, assigns OBJ to contents of a free slot in TABLE,
;;                   and returns the index of the slot
;;      if full, returns nil
;;  (tam-free TABLE INDEX) =>
;;      if slot at INDEX of TABLE is in use, move to the free list and
;;              return the object formerly held by the slot
;;      if slot is already free, signal an error
;;  (tam-table-free-list TABLE) => list of free indices in TABLE
;;  (tam-table-live-list TABLE) => list of in-use indices in TABLE

Thanks,
Lynn

Re: [GNU ELPA] New package: tam

[Philip Kaludercic]

[-- Attachment #1: Type: text/plain, Size: 245 bytes --]

Lynn Winebarger <owinebar@gmail.com> writes:

> I'd like to submit "tam" (table allocation manager) for inclusion in
> GNU ELPA.  The source is available at
> https://github.com/owinebar/emacs-table-allocation-manager

Here are a few comments:


[-- Attachment #2: Type: text/plain, Size: 5048 bytes --]

diff --git a/table-allocation-manager.el b/table-allocation-manager.el
index 59a5718..286c9a2 100644
--- a/table-allocation-manager.el
+++ b/table-allocation-manager.el
@@ -3,6 +3,10 @@
 ;; Copyright (C) 2023  Onnie Lynn Winebarger
 
 ;; Author: Onnie Lynn Winebarger <owinebar@gmail.com>
+;; Maintainer: Onnie Lynn Winebarger <owinebar@gmail.com>
+;; URL: https://github.com/owinebar/emacs-table-allocation-manager
+;; Package-Requires: ((emacs "24.4") (queue "0.2"))
+
 ;; Keywords: lisp, tools
 
 ;; This program is free software; you can redistribute it and/or modify
@@ -24,7 +28,9 @@
 ;; table.  All allocation is done during initialization to avoid triggering
 ;; garbage collection during allocation/free operations.
 
-;;  API:
+;;  API: (is it necessary to document the API here?  This has to be
+;;  kept up to date, while a M-x apropos-function tam- RET could avoid
+;;  the issue.)
 ;;
 ;;  (tam-create-table N) => table of size N
 ;;  (tam-table-fullp TABLE) => nil unless TABLE is full
@@ -43,13 +49,12 @@
 ;;  (tam-table-free-list TABLE) => list of free indices in TABLE
 ;;  (tam-table-live-list TABLE) => list of in-use indices in TABLE
 
-
 ;;; Code:
 
 (eval-when-compile
   (require 'cl-lib))
 
-(require 'queue)
+(require 'queue)			;is this even necessary?  see below.
 
 (cl-defstruct (tam--table (:constructor tam--table-create (size))
 			  (:copier tam--copy-table))
@@ -66,16 +71,15 @@
 				       (table index in-use next previous))
 			(:copier tam--copy-slot))
   "Slot in TAM table"
-  table  ;; table containing this slot
-  index  ;; index of slot in table
-  in-use ;; flag indicating if contents are "live"
-  next   ;; next on list of used/free
-  previous ;; previous on list of used/free
-  contents ;; contents of slot
-  )
+  (table	:documentation "table containing this slot")
+  (index	:documentation "index of slot in table")
+  (in-use	:documentation "flag indicating if contents are live")
+  (next		:documentation "next on list of used/free")
+  (previous	:documentation "previous on list of used/free")
+  (contents	:documentation "contents of slot"))
 
 (defun tam-create-table (N)
-  "Make a tam table of size N."
+  "Make a tam table of size N."		;"tam table" might not be clear.
   (let ((tbl (tam--table-create N))
 	(v (make-vector N nil))
 	(N-1 (- N 1))
@@ -98,8 +102,6 @@
     (setf (tam--table-last-free tbl) (aref v N-1))
     tbl))
 
-
-
 (defun tam-table-fullp (tbl)
   "Test if TBL is full."
   (<= (tam--table-size tbl) (tam--table-used tbl)))
@@ -108,22 +110,20 @@
   "Test if TBL is empty."
   (= (tam--table-used tbl) 0))
 
-(defsubst tam-table-size (tbl)
+(defsubst tam-table-size (tbl)		;why not `defalias'
   "Number of slots in TBL."
   (tam--table-size tbl))
 
-
 (defsubst tam-table-used (tbl)
   "Number of slots of TBL in use."
   (tam--table-used tbl))
 
 (defun tam--table-get-slot (tbl idx)
-  "Get slot IDX of TBL"
+  "Get slot IDX of TBL."
   (aref (tam--table-slots tbl) idx))
 
-
 (defun tam-table-get (tbl idx)
-  "Get contents of slot IDX of TBL"
+  "Get contents of slot IDX of TBL."
   (tam--slot-contents (aref (tam--table-slots tbl) idx)))
 
 (defun tam-allocate (tbl obj)
@@ -133,9 +133,14 @@ Returns index or nil if table is full."
 	next idx)
     (when (not (tam-table-fullp tbl))
       (setf (tam--slot-previous s) (tam--table-last-used tbl))
-      (if (tam-table-emptyp tbl)
-	  (setf (tam--table-first-used tbl) s)
-	(setf (tam--slot-next (tam--table-last-used tbl)) s))
+      (setf (if (tam-table-emptyp tbl)
+		(tam--table-first-used tbl)
+	      (tam--slot-next (tam--table-last-used tbl)))
+	    s)
+      (setf (if (tam-table-emptyp tbl)
+		(tam--table-first-used tbl)
+	      (tam--slot-next (tam--table-last-used tbl)))
+	    s)
       (setf (tam--table-last-used tbl) s)
       (setq next (tam--slot-next s))
       (setf (tam--table-first-free tbl) next)
@@ -151,8 +156,9 @@ Returns index or nil if table is full."
     idx))
 
 (defun tam-free (tbl idx)
-  "Free slot at IDX in TBL.  Returns contents of slot IDX.
-Signals an error if IDX is not in use."
+  "Free slot at IDX in TBL.
+Returns contents of slot IDX.  Signals an error if IDX is not in
+use."
   (let ((s (tam--table-get-slot tbl idx))
 	(last-free (tam--table-last-free tbl))
 	prev next obj)
@@ -185,17 +191,19 @@ Signals an error if IDX is not in use."
     (cl-decf (tam--table-used tbl))
     obj))
 
+;; you appear to only use the queue to track a list of objects, right?
+;; Why not this then:
 (defun tam-table-free-list (tbl)
-  "Return list of free indices in TBL"
+  "Return list of free indices in TBL."
   (let ((s (tam--table-first-free tbl))
-	(q (queue-create)))
+	(q '()))
     (while s
-      (queue-enqueue q (tam--slot-index s))
+      (push (tam--slot-index s) q)
       (setq s (tam--slot-next s)))
-    (queue-all q)))
+    (nreverse q)))			;iff even necessary
 
 (defun tam-table-live-list (tbl)
-  "Return list of live indices in TBL"
+  "Return list of live indices in TBL."
   (let ((s (tam--table-first-used tbl))
 	(q (queue-create)))
     (while s

[-- Attachment #3: Type: text/plain, Size: 23 bytes --]


-- 
Philip Kaludercic

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Mon, Sep 18, 2023 at 5:37 AM Philip Kaludercic <philipk@posteo.net> wrote:
>
> Lynn Winebarger <owinebar@gmail.com> writes:
>
> > I'd like to submit "tam" (table allocation manager) for inclusion in
> > GNU ELPA.  The source is available at
> > https://github.com/owinebar/emacs-table-allocation-manager
>
> Here are a few comments:
Thanks for taking a look.

>
> diff --git a/table-allocation-manager.el b/table-allocation-manager.el
> index 59a5718..286c9a2 100644
> --- a/table-allocation-manager.el
> +++ b/table-allocation-manager.el
> @@ -3,6 +3,10 @@
>  ;; Copyright (C) 2023  Onnie Lynn Winebarger
>
>  ;; Author: Onnie Lynn Winebarger <owinebar@gmail.com>
> +;; Maintainer: Onnie Lynn Winebarger <owinebar@gmail.com>
> +;; URL: https://github.com/owinebar/emacs-table-allocation-manager
> +;; Package-Requires: ((emacs "24.4") (queue "0.2"))
> +

Apologies, I renamed the library to tam.el and failed to note the
changes I made to the renamed file did not get committed and pushed.

>  ;; Keywords: lisp, tools
>
>  ;; This program is free software; you can redistribute it and/or modify
> @@ -24,7 +28,9 @@
>  ;; table.  All allocation is done during initialization to avoid triggering
>  ;; garbage collection during allocation/free operations.
>
> -;;  API:
> +;;  API: (is it necessary to document the API here?  This has to be
> +;;  kept up to date, while a M-x apropos-function tam- RET could avoid
> +;;  the issue.)

I thought it would be helpful to summarize the functionality for review.

>  ;;
>  ;;  (tam-create-table N) => table of size N
>  ;;  (tam-table-fullp TABLE) => nil unless TABLE is full
> @@ -43,13 +49,12 @@
>  ;;  (tam-table-free-list TABLE) => list of free indices in TABLE
>  ;;  (tam-table-live-list TABLE) => list of in-use indices in TABLE
>
> -
>  ;;; Code:
>
>  (eval-when-compile
>    (require 'cl-lib))
>
> -(require 'queue)
> +(require 'queue)                       ;is this even necessary?  see below.

If it's a big deal, then no.  Since queue is a GNU package, I
preferred to not repeat code.

>
>  (cl-defstruct (tam--table (:constructor tam--table-create (size))
>                           (:copier tam--copy-table))
> @@ -66,16 +71,15 @@
>                                        (table index in-use next previous))
>                         (:copier tam--copy-slot))
>    "Slot in TAM table"
> -  table  ;; table containing this slot
> -  index  ;; index of slot in table
> -  in-use ;; flag indicating if contents are "live"
> -  next   ;; next on list of used/free
> -  previous ;; previous on list of used/free
> -  contents ;; contents of slot
> -  )
> +  (table       :documentation "table containing this slot")
> +  (index       :documentation "index of slot in table")
> +  (in-use      :documentation "flag indicating if contents are live")
> +  (next                :documentation "next on list of used/free")
> +  (previous    :documentation "previous on list of used/free")
> +  (contents    :documentation "contents of slot"))
>
>  (defun tam-create-table (N)
> -  "Make a tam table of size N."
> +  "Make a tam table of size N."                ;"tam table" might not be clear.
>    (let ((tbl (tam--table-create N))
>         (v (make-vector N nil))
>         (N-1 (- N 1))
> @@ -98,8 +102,6 @@
>      (setf (tam--table-last-free tbl) (aref v N-1))
>      tbl))
>
> -
> -
>  (defun tam-table-fullp (tbl)
>    "Test if TBL is full."
>    (<= (tam--table-size tbl) (tam--table-used tbl)))
> @@ -108,22 +110,20 @@
>    "Test if TBL is empty."
>    (= (tam--table-used tbl) 0))
>
> -(defsubst tam-table-size (tbl)
> +(defsubst tam-table-size (tbl)         ;why not `defalias'

I tried defalias first, but got a byte-compiler error about a void
variable.  Which I found confusing, since it should be looking for a
function definition, not a variable.  I'm using 28.3.
Some of the following should have already been fixed from when I ran checkdoc.

>    "Number of slots in TBL."
>    (tam--table-size tbl))
>
> -
>  (defsubst tam-table-used (tbl)
>    "Number of slots of TBL in use."
>    (tam--table-used tbl))
>
>  (defun tam--table-get-slot (tbl idx)
> -  "Get slot IDX of TBL"
> +  "Get slot IDX of TBL."
>    (aref (tam--table-slots tbl) idx))
>
> -
>  (defun tam-table-get (tbl idx)
> -  "Get contents of slot IDX of TBL"
> +  "Get contents of slot IDX of TBL."
>    (tam--slot-contents (aref (tam--table-slots tbl) idx)))
>
>  (defun tam-allocate (tbl obj)
> @@ -133,9 +133,14 @@ Returns index or nil if table is full."
>         next idx)
>      (when (not (tam-table-fullp tbl))
>        (setf (tam--slot-previous s) (tam--table-last-used tbl))
> -      (if (tam-table-emptyp tbl)
> -         (setf (tam--table-first-used tbl) s)
> -       (setf (tam--slot-next (tam--table-last-used tbl)) s))
> +      (setf (if (tam-table-emptyp tbl)
> +               (tam--table-first-used tbl)
> +             (tam--slot-next (tam--table-last-used tbl)))
> +           s)

Is this a personal stylistic preference, or a requirement?  I'll
change it if required, but I find computing the place inside a set
form to be disconcerting if it's not required.  For example, I
wouldn't use a set form like
(set (if P 'A 'B) some-value)
in place of
(if P (setq A some-value) (setq B some-value))

where I might be amenable to
(set (opaque-function-call args ...) some-value)

> +      (setf (if (tam-table-emptyp tbl)
> +               (tam--table-first-used tbl)
> +             (tam--slot-next (tam--table-last-used tbl)))
> +           s)
I'm assuming this is a typo.

>        (setf (tam--table-last-used tbl) s)
>        (setq next (tam--slot-next s))
>        (setf (tam--table-first-free tbl) next)
> @@ -151,8 +156,9 @@ Returns index or nil if table is full."
>      idx))
>
>  (defun tam-free (tbl idx)
> -  "Free slot at IDX in TBL.  Returns contents of slot IDX.
> -Signals an error if IDX is not in use."
> +  "Free slot at IDX in TBL.
> +Returns contents of slot IDX.  Signals an error if IDX is not in
> +use."
>    (let ((s (tam--table-get-slot tbl idx))
>         (last-free (tam--table-last-free tbl))
>         prev next obj)
> @@ -185,17 +191,19 @@ Signals an error if IDX is not in use."
>      (cl-decf (tam--table-used tbl))
>      obj))
>
> +;; you appear to only use the queue to track a list of objects, right?
> +;; Why not this then:
>  (defun tam-table-free-list (tbl)
> -  "Return list of free indices in TBL"
> +  "Return list of free indices in TBL."
>    (let ((s (tam--table-first-free tbl))
> -       (q (queue-create)))
> +       (q '()))
>      (while s
> -      (queue-enqueue q (tam--slot-index s))
> +      (push (tam--slot-index s) q)
>        (setq s (tam--slot-next s)))
> -    (queue-all q)))
> +    (nreverse q)))                     ;iff even necessary

I do want to return lists reflecting the ordering of the slots.  I am
not a fan of constructing an ordered structure only to reverse it.
I can rewrite this to append to the tail using let-bound head and tail
variables, but it seems excessive to avoid a single allocation of a
queue structure.
That said, these functions are primarily intended for debugging.
>
>  (defun tam-table-live-list (tbl)
> -  "Return list of live indices in TBL"
> +  "Return list of live indices in TBL."
>    (let ((s (tam--table-first-used tbl))
>         (q (queue-create)))
>      (while s
>
> --
> Philip Kaludercic

Re: [GNU ELPA] New package: tam

[Philip Kaludercic]

Lynn Winebarger <owinebar@gmail.com> writes:

> On Mon, Sep 18, 2023 at 5:37 AM Philip Kaludercic <philipk@posteo.net> wrote:
>>
>> Lynn Winebarger <owinebar@gmail.com> writes:
>>
>> > I'd like to submit "tam" (table allocation manager) for inclusion in
>> > GNU ELPA.  The source is available at
>> > https://github.com/owinebar/emacs-table-allocation-manager
>>
>> Here are a few comments:
> Thanks for taking a look.
>
>>
>> diff --git a/table-allocation-manager.el b/table-allocation-manager.el
>> index 59a5718..286c9a2 100644
>> --- a/table-allocation-manager.el
>> +++ b/table-allocation-manager.el
>> @@ -3,6 +3,10 @@
>>  ;; Copyright (C) 2023  Onnie Lynn Winebarger
>>
>>  ;; Author: Onnie Lynn Winebarger <owinebar@gmail.com>
>> +;; Maintainer: Onnie Lynn Winebarger <owinebar@gmail.com>
>> +;; URL: https://github.com/owinebar/emacs-table-allocation-manager
>> +;; Package-Requires: ((emacs "24.4") (queue "0.2"))
>> +
>
> Apologies, I renamed the library to tam.el and failed to note the
> changes I made to the renamed file did not get committed and pushed.

So what does that mean?

>>  ;; Keywords: lisp, tools
>>
>>  ;; This program is free software; you can redistribute it and/or modify
>> @@ -24,7 +28,9 @@
>>  ;; table.  All allocation is done during initialization to avoid triggering
>>  ;; garbage collection during allocation/free operations.
>>
>> -;;  API:
>> +;;  API: (is it necessary to document the API here?  This has to be
>> +;;  kept up to date, while a M-x apropos-function tam- RET could avoid
>> +;;  the issue.)
>
> I thought it would be helpful to summarize the functionality for review.

That is true, but I wouldn't bother with maintaining this in the long
term.  Encouraging the usage of apropos commands is good anyway.

>>  ;;
>>  ;;  (tam-create-table N) => table of size N
>>  ;;  (tam-table-fullp TABLE) => nil unless TABLE is full
>> @@ -43,13 +49,12 @@
>>  ;;  (tam-table-free-list TABLE) => list of free indices in TABLE
>>  ;;  (tam-table-live-list TABLE) => list of in-use indices in TABLE
>>
>> -
>>  ;;; Code:
>>
>>  (eval-when-compile
>>    (require 'cl-lib))
>>
>> -(require 'queue)
>> +(require 'queue)                       ;is this even necessary?  see below.
>
> If it's a big deal, then no.  Since queue is a GNU package, I
> preferred to not repeat code.

I am the kind of person who thinks twice about installing a package when
it has dependencies.  But if you prefer to use a package available on
ELPA, then that is of course OK as well.

>>
>>  (cl-defstruct (tam--table (:constructor tam--table-create (size))
>>                           (:copier tam--copy-table))
>> @@ -66,16 +71,15 @@
>>                                        (table index in-use next previous))
>>                         (:copier tam--copy-slot))
>>    "Slot in TAM table"
>> -  table  ;; table containing this slot
>> -  index  ;; index of slot in table
>> -  in-use ;; flag indicating if contents are "live"
>> -  next   ;; next on list of used/free
>> -  previous ;; previous on list of used/free
>> -  contents ;; contents of slot
>> -  )
>> +  (table       :documentation "table containing this slot")
>> +  (index       :documentation "index of slot in table")
>> +  (in-use      :documentation "flag indicating if contents are live")
>> +  (next                :documentation "next on list of used/free")
>> +  (previous    :documentation "previous on list of used/free")
>> +  (contents    :documentation "contents of slot"))
>>
>>  (defun tam-create-table (N)
>> -  "Make a tam table of size N."
>> +  "Make a tam table of size N."                ;"tam table" might not be clear.
>>    (let ((tbl (tam--table-create N))
>>         (v (make-vector N nil))
>>         (N-1 (- N 1))
>> @@ -98,8 +102,6 @@
>>      (setf (tam--table-last-free tbl) (aref v N-1))
>>      tbl))
>>
>> -
>> -
>>  (defun tam-table-fullp (tbl)
>>    "Test if TBL is full."
>>    (<= (tam--table-size tbl) (tam--table-used tbl)))
>> @@ -108,22 +110,20 @@
>>    "Test if TBL is empty."
>>    (= (tam--table-used tbl) 0))
>>
>> -(defsubst tam-table-size (tbl)
>> +(defsubst tam-table-size (tbl)         ;why not `defalias'
>
> I tried defalias first, but got a byte-compiler error about a void
> variable.  Which I found confusing, since it should be looking for a
> function definition, not a variable.  I'm using 28.3.
> Some of the following should have already been fixed from when I ran checkdoc.

What did you do?  That sounds like something was misquoted:

(defalias 'tam-table-size #'tam--table-size)

?

>>    "Number of slots in TBL."
>>    (tam--table-size tbl))
>>
>> -
>>  (defsubst tam-table-used (tbl)
>>    "Number of slots of TBL in use."
>>    (tam--table-used tbl))
>>
>>  (defun tam--table-get-slot (tbl idx)
>> -  "Get slot IDX of TBL"
>> +  "Get slot IDX of TBL."
>>    (aref (tam--table-slots tbl) idx))
>>
>> -
>>  (defun tam-table-get (tbl idx)
>> -  "Get contents of slot IDX of TBL"
>> +  "Get contents of slot IDX of TBL."
>>    (tam--slot-contents (aref (tam--table-slots tbl) idx)))
>>
>>  (defun tam-allocate (tbl obj)
>> @@ -133,9 +133,14 @@ Returns index or nil if table is full."
>>         next idx)
>>      (when (not (tam-table-fullp tbl))
>>        (setf (tam--slot-previous s) (tam--table-last-used tbl))
>> -      (if (tam-table-emptyp tbl)
>> -         (setf (tam--table-first-used tbl) s)
>> -       (setf (tam--slot-next (tam--table-last-used tbl)) s))
>> +      (setf (if (tam-table-emptyp tbl)
>> +               (tam--table-first-used tbl)
>> +             (tam--slot-next (tam--table-last-used tbl)))
>> +           s)
>
> Is this a personal stylistic preference, or a requirement?  

Nothing I say is a requirement, I should have made that explicit.  More
of a "look what you could also do, in case you are interested".

>                                                             I'll
> change it if required, but I find computing the place inside a set
> form to be disconcerting if it's not required.  For example, I
> wouldn't use a set form like
> (set (if P 'A 'B) some-value)
> in place of
> (if P (setq A some-value) (setq B some-value))

In that case, is there a reason you are using setf?

> where I might be amenable to
> (set (opaque-function-call args ...) some-value)
>
>> +      (setf (if (tam-table-emptyp tbl)
>> +               (tam--table-first-used tbl)
>> +             (tam--slot-next (tam--table-last-used tbl)))
>> +           s)
> I'm assuming this is a typo.

Probably.

>>        (setf (tam--table-last-used tbl) s)
>>        (setq next (tam--slot-next s))
>>        (setf (tam--table-first-free tbl) next)
>> @@ -151,8 +156,9 @@ Returns index or nil if table is full."
>>      idx))
>>
>>  (defun tam-free (tbl idx)
>> -  "Free slot at IDX in TBL.  Returns contents of slot IDX.
>> -Signals an error if IDX is not in use."
>> +  "Free slot at IDX in TBL.
>> +Returns contents of slot IDX.  Signals an error if IDX is not in
>> +use."
>>    (let ((s (tam--table-get-slot tbl idx))
>>         (last-free (tam--table-last-free tbl))
>>         prev next obj)
>> @@ -185,17 +191,19 @@ Signals an error if IDX is not in use."
>>      (cl-decf (tam--table-used tbl))
>>      obj))
>>
>> +;; you appear to only use the queue to track a list of objects, right?
>> +;; Why not this then:
>>  (defun tam-table-free-list (tbl)
>> -  "Return list of free indices in TBL"
>> +  "Return list of free indices in TBL."
>>    (let ((s (tam--table-first-free tbl))
>> -       (q (queue-create)))
>> +       (q '()))
>>      (while s
>> -      (queue-enqueue q (tam--slot-index s))
>> +      (push (tam--slot-index s) q)
>>        (setq s (tam--slot-next s)))
>> -    (queue-all q)))
>> +    (nreverse q)))                     ;iff even necessary
>
> I do want to return lists reflecting the ordering of the slots.  I am
> not a fan of constructing an ordered structure only to reverse it.

FWIW this is standard practice, and what a cl-loop with collect would
also expand to.  And if I am not mistaken, this is more efficient, than
accumulating a linked list in the right order to begin with (it is a
difference of O(n) vs O(n^2), I believe).

> I can rewrite this to append to the tail using let-bound head and tail
> variables, but it seems excessive to avoid a single allocation of a
> queue structure.
> That said, these functions are primarily intended for debugging.

Wouldn't that kind of a convenience be an argument against adding an
extra dependency?

>>
>>  (defun tam-table-live-list (tbl)
>> -  "Return list of live indices in TBL"
>> +  "Return list of live indices in TBL."
>>    (let ((s (tam--table-first-used tbl))
>>         (q (queue-create)))
>>      (while s
>>
>> --
>> Philip Kaludercic

-- 
Philip Kaludercic

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Mon, Sep 18, 2023 at 1:02 PM Philip Kaludercic <philipk@posteo.net> wrote:
> > Apologies, I renamed the library to tam.el and failed to note the
> > changes I made to the renamed file did not get committed and pushed.
>
> So what does that mean?

That I don't use git enough to avoid rookie errors? I had already
addressed some of the items you brought up in my working copy, they
just hadn't been committed and pushed to the server.
I think I've addressed all the items you brought up in the last
version I pushed.

> I am the kind of person who thinks twice about installing a package when
> it has dependencies.  But if you prefer to use a package available on
> ELPA, then that is of course OK as well.

I revised it to make use of cl-loop per your observation in the
previous email.  I'm not really a fan of the loop imperative DSL, but
this case was simple enough (as you pointed out).
Some packages (like queue) provide pretty basic data structures, so I
think avoiding packages that depend on them only encourages
reimplementing the wheel.
However, I might be the world record holder for the number of elisp
libraries loaded and included in a dump file.
> >> -(defsubst tam-table-size (tbl)
> >> +(defsubst tam-table-size (tbl)         ;why not `defalias'
> >
> > I tried defalias first, but got a byte-compiler error about a void
> > variable.  Which I found confusing, since it should be looking for a
> > function definition, not a variable.  I'm using 28.3.
> > Some of the following should have already been fixed from when I ran checkdoc.
>
> What did you do?  That sounds like something was misquoted:
>
> (defalias 'tam-table-size #'tam--table-size)

I forgot defalias is a function and not a macro.  Thanks.

> >                                                             I'll
> > change it if required, but I find computing the place inside a set
> > form to be disconcerting if it's not required.  For example, I
> > wouldn't use a set form like
> > (set (if P 'A 'B) some-value)
> > in place of
> > (if P (setq A some-value) (setq B some-value))
>
> In that case, is there a reason you are using setf?

I'm confused - the documentation does not indicate that an "if" form
would be a "place" that setf knows how to handle.  The cl-lib doc does
say it extends setf to handle macro expansions, but 'if' is a special
form that does not macro-expand.
I use setf because that's the cleanest way to set fields of a
structure.  It's more like setq than set (it's a macro for one thing)
as far as I can tell.

> > I do want to return lists reflecting the ordering of the slots.  I am
> > not a fan of constructing an ordered structure only to reverse it.
>
> FWIW this is standard practice, and what a cl-loop with collect would
> also expand to.  And if I am not mistaken, this is more efficient, than
> accumulating a linked list in the right order to begin with (it is a
> difference of O(n) vs O(n^2), I believe).

Wait, did you mean cl-loop with collect will do the nreverse?  I
thought you meant it would keep track of the tail of the list and
update it.
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.

> > That said, these functions are primarily intended for debugging.
>
> Wouldn't that kind of a convenience be an argument against adding an
> extra dependency?

Only if I was trying to get a library included in startup.el, or if
the dependency was not in GNU ELPA.  Otherwise, why are people writing
packages?  They are not all stand-alone user interfacing programs.
Some are just basic data structures and algorithms that haven't been
included in core emacs for whatever reason.  Queue is one of those.

Lynn

Re: [GNU ELPA] New package: tam

[Philip Kaludercic]

Lynn Winebarger <owinebar@gmail.com> writes:

> On Mon, Sep 18, 2023 at 1:02 PM Philip Kaludercic <philipk@posteo.net> wrote:
>> > Apologies, I renamed the library to tam.el and failed to note the
>> > changes I made to the renamed file did not get committed and pushed.
>>
>> So what does that mean?
>
> That I don't use git enough to avoid rookie errors? I had already
> addressed some of the items you brought up in my working copy, they
> just hadn't been committed and pushed to the server.
> I think I've addressed all the items you brought up in the last
> version I pushed.

Ok.  What I wanted to make sure was that you didn't change the
repository URL or something like that.

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.

[0] https://github.com/owinebar/emacs-table-allocation-manager/commit/bc654b6d687c67c5ad45218d6f45f95b8f1e0478

>> I am the kind of person who thinks twice about installing a package when
>> it has dependencies.  But if you prefer to use a package available on
>> ELPA, then that is of course OK as well.
>
> I revised it to make use of cl-loop per your observation in the
> previous email.  I'm not really a fan of the loop imperative DSL, but
> this case was simple enough (as you pointed out).
> Some packages (like queue) provide pretty basic data structures, so I
> think avoiding packages that depend on them only encourages
> reimplementing the wheel.
> However, I might be the world record holder for the number of elisp
> libraries loaded and included in a dump file.
>> >> -(defsubst tam-table-size (tbl)
>> >> +(defsubst tam-table-size (tbl)         ;why not `defalias'
>> >
>> > I tried defalias first, but got a byte-compiler error about a void
>> > variable.  Which I found confusing, since it should be looking for a
>> > function definition, not a variable.  I'm using 28.3.
>> > Some of the following should have already been fixed from when I
>> > ran checkdoc.
>>
>> What did you do?  That sounds like something was misquoted:
>>
>> (defalias 'tam-table-size #'tam--table-size)
>
> I forgot defalias is a function and not a macro.  Thanks.
>
>> >                                                             I'll
>> > change it if required, but I find computing the place inside a set
>> > form to be disconcerting if it's not required.  For example, I
>> > wouldn't use a set form like
>> > (set (if P 'A 'B) some-value)
>> > in place of
>> > (if P (setq A some-value) (setq B some-value))
>>
>> In that case, is there a reason you are using setf?
>
> I'm confused - the documentation does not indicate that an "if" form
> would be a "place" that setf knows how to handle.  The cl-lib doc does
> say it extends setf to handle macro expansions, but 'if' is a special
> form that does not macro-expand.
> I use setf because that's the cleanest way to set fields of a
> structure.  It's more like setq than set (it's a macro for one thing)
> as far as I can tell.

The question was supposed to be more general, sorry for the confusion.
I wanted to know if there was a reason you were using setf even when
setq would be enough, but it really doesn't matter either way since setf
on a symbol expands directly to setq.

>> > I do want to return lists reflecting the ordering of the slots.  I am
>> > not a fan of constructing an ordered structure only to reverse it.
>>
>> FWIW this is standard practice, and what a cl-loop with collect would
>> also expand to.  And if I am not mistaken, this is more efficient, than
>> accumulating a linked list in the right order to begin with (it is a
>> difference of O(n) vs O(n^2), I believe).
>
> Wait, did you mean cl-loop with collect will do the nreverse?  I
> thought you meant it would keep track of the tail of the list and
> update it.

No, it uses nreverse:

--8<---------------cut here---------------start------------->8---
(macroexpand-all '(cl-loop for i to 10 collect i))
(let* ((i 0) (--cl-var-- nil))
  (while (<= i 10)
    (setq --cl-var-- (cons i --cl-var--))
    (setq i (+ i 1)))
  (nreverse --cl-var--))
--8<---------------cut here---------------end--------------->8---

> 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.
>
>> > That said, these functions are primarily intended for debugging.
>>
>> Wouldn't that kind of a convenience be an argument against adding an
>> extra dependency?
>
> Only if I was trying to get a library included in startup.el, or if
> the dependency was not in GNU ELPA.  Otherwise, why are people writing
> packages?  They are not all stand-alone user interfacing programs.
> Some are just basic data structures and algorithms that haven't been
> included in core emacs for whatever reason.  Queue is one of those.

These kinds of arguments lead to leftpad like situations, where people
defer any slightly complicated functionality to a library.  The last
thing I want to see when installing a package is that it drags along
dozens or even hundreds of recursive dependants, causing me to loose an
overview of what I have installed and what is being installed.  Every
dependency a package brings with it (especially packages like dash &
co.) is an argument against using it, imo.

> Lynn

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Wed, Sep 20, 2023 at 4:26 AM Philip Kaludercic <philipk@posteo.net> 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.  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.

I rewrote the code so the only appearances of the call operator in the
byte-code of those functions is for error signaling.  I also provide
an inlining version of each operation so library clients can avoid
call instructions in their code.

> >> I am the kind of person who thinks twice about installing a package when
> >> it has dependencies.  But if you prefer to use a package available on
> >> ELPA, then that is of course OK as well.

BTW, there's something ironic about this, since you actually appear to
review most packages on GNU/NonGNU ELPA - how many users would be more
familiar with the packages that might be installed from those
archives?
At any rate, it does not depend on any packages, or even cl-lib, now -
though I have to revise the header to say so.

>
> The question was supposed to be more general, sorry for the confusion.
> I wanted to know if there was a reason you were using setf even when
> setq would be enough, but it really doesn't matter either way since setf
> on a symbol expands directly to setq.

If I had setf on a symbol, it was a typo.  They are all gone now,
since they did not get optimized out.

> No, it uses nreverse:
>
> --8<---------------cut here---------------start------------->8---
> (macroexpand-all '(cl-loop for i to 10 collect i))
> (let* ((i 0) (--cl-var-- nil))
>   (while (<= i 10)
>     (setq --cl-var-- (cons i --cl-var--))
>     (setq i (+ i 1)))
>   (nreverse --cl-var--))
> --8<---------------cut here---------------end--------------->8---
Blech, I replaced it with a simple function.

> These kinds of arguments lead to leftpad like situations, where people
> defer any slightly complicated functionality to a library.  The last
> thing I want to see when installing a package is that it drags along
> dozens or even hundreds of recursive dependants, causing me to loose an
> overview of what I have installed and what is being installed.  Every
> dependency a package brings with it (especially packages like dash &
> co.) is an argument against using it, imo.

I don't think the leftpad situation (which I had to look up) can
happen on GNU ELPA.  Even if, despite the FSF's precautions, something
had to be removed, I'm sure there would be plenty of warning.

Lynn

Re: [GNU ELPA] New package: tam

[Stefan Monnier via Emacs development discussions.]

>> 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?

> 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.

> 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 :-)


        Stefan

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

[-- Attachment #1: Type: text/plain, Size: 3453 bytes --]

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

[-- Attachment #2: disassembled-cl-defstruct-tam-free.txt --]
[-- Type: text/plain, Size: 6241 bytes --]

byte code for tam-free:
  doc:  Free slot at IDX in TBL. ...
  args: (arg1 arg2)
0	constant  tam--table-get-slot
1	stack-ref 2
2	stack-ref 2
3	call	  2
4	constant  type-of
5	stack-ref 3
6	call	  1
7	varref	  cl-struct-tam--table-tags
8	memq
9	goto-if-not-nil 1
12	constant  signal
13	constant  wrong-type-argument
14	constant  tam--table
15	stack-ref 5
16	list2
17	call	  2
18	discard
19:1	stack-ref 2
20	constant  5
21	aref
22	constant  nil
23	dup
24	dup
25	constant  type-of
26	stack-ref 5
27	call	  1
28	varref	  cl-struct-tam--slot-tags
29	memq
30	goto-if-not-nil 2
33	constant  signal
34	constant  wrong-type-argument
35	constant  tam--slot
36	stack-ref 7
38	list2
39	call	  2
40	discard
41:2	stack-ref 4
42	constant  3
43	aref
44	goto-if-not-nil 3
47	constant  signal
48	constant  tam-already-free
49	constant  format
50	constant  "Attempt to free unused table entry %s"
51	stack-ref 9
53	call	  2
54	call	  2
55	discard
56:3	constant  type-of
57	stack-ref 5
58	call	  1
59	varref	  cl-struct-tam--slot-tags
60	memq
61	goto-if-not-nil 4
64	constant  signal
65	constant  wrong-type-argument
66	constant  tam--slot
67	stack-ref 7
69	list2
70	call	  2
71	discard
72:4	stack-ref 4
73	constant  5
74	aref
75	stack-set 3
77	constant  type-of
78	stack-ref 5
79	call	  1
80	varref	  cl-struct-tam--slot-tags
81	memq
82	goto-if-not-nil 5
85	constant  signal
86	constant  wrong-type-argument
87	constant  tam--slot
88	stack-ref 7
90	list2
91	call	  2
92	discard
93:5	stack-ref 4
94	constant  4
95	aref
96	stack-set 2
98	constant  type-of
99	stack-ref 5
100	call	  1
101	varref	  cl-struct-tam--slot-tags
102	memq
103	goto-if-not-nil 6
106	constant  signal
107	constant  wrong-type-argument
108	constant  tam--slot
109	stack-ref 7
111	list2
112	call	  2
113	discard
114:6	stack-ref 4
115	constant  6
116	aref
117	stack-set 1
119	constant  type-of
120	stack-ref 5
121	call	  1
122	varref	  cl-struct-tam--slot-tags
123	memq
124	goto-if-not-nil 7
127	constant  signal
128	constant  wrong-type-argument
129	constant  tam--slot
130	stack-ref 7
132	list2
133	call	  2
134	discard
135:7	stack-ref 4
136	constant  4
137	constant  nil
138	aset
139	discard
140	stack-ref 2
141	goto-if-nil 9
144	constant  type-of
145	stack-ref 3
146	call	  1
147	varref	  cl-struct-tam--slot-tags
148	memq
149	goto-if-not-nil 8
152	constant  signal
153	constant  wrong-type-argument
154	constant  tam--slot
155	stack-ref 5
156	list2
157	call	  2
158	discard
159:8	stack-ref 2
160	constant  4
161	stack-ref 3
162	aset
163	discard
164	goto	  11
167:9	constant  type-of
168	stack-ref 7
170	call	  1
171	varref	  cl-struct-tam--table-tags
172	memq
173	goto-if-not-nil 10
176	constant  signal
177	constant  wrong-type-argument
178	constant  tam--table
179	stack-ref 9
181	list2
182	call	  2
183	discard
184:10	stack-ref 6
186	constant  6
187	stack-ref 3
188	aset
189	discard
190:11	stack-ref 1
191	goto-if-nil 13
194	constant  type-of
195	stack-ref 2
196	call	  1
197	varref	  cl-struct-tam--slot-tags
198	memq
199	goto-if-not-nil 12
202	constant  signal
203	constant  wrong-type-argument
204	constant  tam--slot
205	stack-ref 4
206	list2
207	call	  2
208	discard
209:12	stack-ref 1
210	constant  5
211	stack-ref 4
212	aset
213	discard
214	goto	  15
217:13	constant  type-of
218	stack-ref 7
220	call	  1
221	varref	  cl-struct-tam--table-tags
222	memq
223	goto-if-not-nil 14
226	constant  signal
227	constant  wrong-type-argument
228	constant  tam--table
229	stack-ref 9
231	list2
232	call	  2
233	discard
234:14	stack-ref 6
236	constant  7
237	stack-ref 4
238	aset
239	discard
240:15	stack-ref 3
241	goto-if-nil 18
244	constant  type-of
245	stack-ref 4
246	call	  1
247	varref	  cl-struct-tam--slot-tags
248	memq
249	goto-if-not-nil 16
252	constant  signal
253	constant  wrong-type-argument
254	constant  tam--slot
255	stack-ref 6
257	list2
258	call	  2
259	discard
260:16	stack-ref 3
261	constant  4
262	stack-ref 6
264	aset
265	discard
266	constant  type-of
267	stack-ref 5
268	call	  1
269	varref	  cl-struct-tam--slot-tags
270	memq
271	goto-if-not-nil 17
274	constant  signal
275	constant  wrong-type-argument
276	constant  tam--slot
277	stack-ref 7
279	list2
280	call	  2
281	discard
282:17	stack-ref 4
283	constant  5
284	stack-ref 5
285	aset
286	discard
287	goto	  21
290:18	constant  type-of
291	stack-ref 7
293	call	  1
294	varref	  cl-struct-tam--table-tags
295	memq
296	goto-if-not-nil 19
299	constant  signal
300	constant  wrong-type-argument
301	constant  tam--table
302	stack-ref 9
304	list2
305	call	  2
306	discard
307:19	stack-ref 6
309	constant  4
310	stack-ref 6
312	aset
313	discard
314	constant  type-of
315	stack-ref 5
316	call	  1
317	varref	  cl-struct-tam--slot-tags
318	memq
319	goto-if-not-nil 20
322	constant  signal
323	constant  wrong-type-argument
324	constant  tam--slot
325	stack-ref 7
327	list2
328	call	  2
329	discard
330:20	stack-ref 4
331	constant  5
332	constant  nil
333	aset
334	discard
335:21	constant  type-of
336	stack-ref 7
338	call	  1
339	varref	  cl-struct-tam--table-tags
340	memq
341	goto-if-not-nil 22
344	constant  signal
345	constant  wrong-type-argument
346	constant  tam--table
347	stack-ref 9
349	list2
350	call	  2
351	discard
352:22	stack-ref 6
354	constant  5
355	stack-ref 6
357	aset
358	discard
359	constant  type-of
360	stack-ref 5
361	call	  1
362	varref	  cl-struct-tam--slot-tags
363	memq
364	goto-if-not-nil 23
367	constant  signal
368	constant  wrong-type-argument
369	constant  tam--slot
370	stack-ref 7
372	list2
373	call	  2
374	discard
375:23	stack-ref 4
376	constant  3
377	constant  nil
378	aset
379	discard
380	constant  type-of
381	stack-ref 5
382	call	  1
383	varref	  cl-struct-tam--slot-tags
384	memq
385	goto-if-not-nil 24
388	constant  signal
389	constant  wrong-type-argument
390	constant  tam--slot
391	stack-ref 7
393	list2
394	call	  2
395	discard
396:24	stack-ref 4
397	constant  6
398	constant  nil
399	aset
400	discard
401	constant  type-of
402	stack-ref 7
404	call	  1
405	varref	  cl-struct-tam--table-tags
406	memq
407	goto-if-not-nil 25
410	constant  signal
411	constant  wrong-type-argument
412	constant  tam--table
413	stack-ref 9
415	list2
416	call	  2
417	discard
418:25	stack-ref 6
420	constant  2
421	stack-ref 8
423	constant  2
424	aref
425	sub1
426	aset
427	discard
428	return

[-- Attachment #3: disassembled-no-cl-lib-tam-free.txt --]
[-- Type: text/plain, Size: 2419 bytes --]

byte code for tam-free:
  args: (arg1 arg2)
0	stack-ref 1
1	stack-ref 1
2	stack-ref 1
3	dup
4	stack-ref 2
5	stack-ref 1
6	dup
7	constant  3
8	aref
9	stack-set 1
11	stack-ref 1
12	aref
13	discardN-preserve-tos 2
15	stack-ref 1
16	dup
17	constant  5
18	aref
19	stack-set 1
21	stack-ref 1
22	dup
23	constant  2
24	aref
25	stack-set 1
27	constant  nil
28	dup
29	stack-ref 4
30	dup
31	constant  3
32	aref
33	stack-set 1
35	goto-if-not-nil 1
38	constant  signal
39	constant  tam-already-free
40	constant  format
41	constant  "Attempt to free unused table entry %s"
42	stack-ref 6
44	call	  2
45	call	  2
46	discard
47:1	stack-ref 4
48	dup
49	constant  5
50	aref
51	stack-set 1
53	stack-set 2
55	stack-ref 4
56	dup
57	constant  4
58	aref
59	stack-set 1
61	stack-set 1
63	stack-ref 4
64	constant  nil
65	stack-ref 1
66	constant  4
67	stack-ref 2
68	aset
69	discardN  3
71	stack-ref 1
72	goto-if-nil 2
75	stack-ref 1
76	stack-ref 1
77	stack-ref 1
78	constant  4
79	stack-ref 2
80	aset
81	discardN  3
83	goto	  3
86:2	stack-ref 5
87	stack-ref 1
88	stack-ref 1
89	constant  6
90	stack-ref 2
91	aset
92	discardN  3
94:3	dup
95	goto-if-nil 4
98	dup
99	stack-ref 2
100	stack-ref 1
101	constant  5
102	stack-ref 2
103	aset
104	discardN  3
106	goto	  5
109:4	stack-ref 5
110	stack-ref 2
111	stack-ref 1
112	constant  7
113	stack-ref 2
114	aset
115	discardN  3
117:5	stack-ref 3
118	goto-if-nil 6
121	stack-ref 3
122	stack-ref 5
123	stack-ref 1
124	constant  4
125	stack-ref 2
126	aset
127	discardN  3
129	stack-ref 4
130	stack-ref 4
131	stack-ref 1
132	constant  5
133	stack-ref 2
134	aset
135	discardN  3
137	goto	  7
140:6	stack-ref 5
141	stack-ref 5
142	stack-ref 1
143	constant  4
144	stack-ref 2
145	aset
146	discardN  3
148	stack-ref 4
149	constant  nil
150	stack-ref 1
151	constant  5
152	stack-ref 2
153	aset
154	discardN  3
156:7	stack-ref 5
157	stack-ref 5
158	stack-ref 1
159	constant  5
160	stack-ref 2
161	aset
162	discardN  3
164	stack-ref 4
165	constant  nil
166	stack-ref 1
167	constant  3
168	stack-ref 2
169	aset
170	discardN  3
172	stack-ref 5
173	dup
174	dup
175	constant  2
176	aref
177	stack-set 1
179	sub1
180	stack-ref 1
181	constant  2
182	stack-ref 2
183	aset
184	discardN  7
186	stack-set 1
188	constant  nil
189	stack-ref 1
190	dup
191	constant  6
192	aref
193	stack-set 1
195	stack-set 1
197	stack-ref 1
198	constant  nil
199	stack-ref 1
200	constant  6
201	stack-ref 2
202	aset
203	discardN  3
205	return

Re: [GNU ELPA] New package: tam

[Stefan Monnier]

> You're correct, the accessors and setfs _are_ inlined as arefs and
> asets.

Thanks for confirming.

> accessor.  There are a lot of type-of, all of which are excessive for
> this type of low-level function.

You might be able to remove those by playing with the optimization
level, e.g.:

    (cl-declaim (optimize (speed 3)))

> 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.

The GC can occur right before or right after since the act of calling
your functions will go through `maybe_gc`, in any case, so I doubt
that will ever make a significant difference.

>> > 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?

Yes.

> 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.

AFAIK, Emacs is not run as a real-time task, so I wonder why you're
worrying about that.
[ And no, an additional stack segment should not trigger GC, AFAIK.  ]


        Stefan

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Thu, Sep 21, 2023 at 9:59 AM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> > 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.
>
> The GC can occur right before or right after since the act of calling
> your functions will go through `maybe_gc`, in any case, so I doubt
> that will ever make a significant difference.

This is true.  Every path to executing a callback will call maybe_quit
and maybe_gc.

> > 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.
>
> AFAIK, Emacs is not run as a real-time task, so I wonder why you're
> worrying about that.
> [ And no, an additional stack segment should not trigger GC, AFAIK.  ]

I want to add minimal overhead so developers will feel free to use it
or other infrastructure packages that make use of it.

I'm also just curious.  Exercises of this sort are a satisfying excuse
to dig into emacs-lisp internals.


Lynn

Re: [GNU ELPA] New package: tam

[Stefan Monnier]

> I'm also just curious.  Exercises of this sort are a satisfying excuse
> to dig into emacs-lisp internals.

Can't argue with that!


        Stefan

Re: [GNU ELPA] New package: tam

[Philip Kaludercic]

Lynn Winebarger <owinebar@gmail.com> writes:

> On Wed, Sep 20, 2023 at 4:26 AM Philip Kaludercic <philipk@posteo.net> 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.  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.
>
> I rewrote the code so the only appearances of the call operator in the
> byte-code of those functions is for error signaling.  I also provide
> an inlining version of each operation so library clients can avoid
> call instructions in their code.

From what I understand this situation was resolved in the other
subthread, right?

>> >> I am the kind of person who thinks twice about installing a package when
>> >> it has dependencies.  But if you prefer to use a package available on
>> >> ELPA, then that is of course OK as well.
>
> BTW, there's something ironic about this, since you actually appear to
> review most packages on GNU/NonGNU ELPA - how many users would be more
> familiar with the packages that might be installed from those
> archives?
> At any rate, it does not depend on any packages, or even cl-lib, now -
> though I have to revise the header to say so.

I don't know if this is ironic or not, I just don't like having too many
packages installed in general?  As I said, this is my personal taste and
I am not forcing this onto anyone.

>>
>> The question was supposed to be more general, sorry for the confusion.
>> I wanted to know if there was a reason you were using setf even when
>> setq would be enough, but it really doesn't matter either way since setf
>> on a symbol expands directly to setq.
>
> If I had setf on a symbol, it was a typo.  They are all gone now,
> since they did not get optimized out.

OK.

>> No, it uses nreverse:
>>
>> --8<---------------cut here---------------start------------->8---
>> (macroexpand-all '(cl-loop for i to 10 collect i))
>> (let* ((i 0) (--cl-var-- nil))
>>   (while (<= i 10)
>>     (setq --cl-var-- (cons i --cl-var--))
>>     (setq i (+ i 1)))
>>   (nreverse --cl-var--))
>> --8<---------------cut here---------------end--------------->8---
> Blech, I replaced it with a simple function.

Another idea could be using mapcan, but usually requires calling a
lambda expression -- at which point we have firmly reached the territory
of micro-optimisation, and it makes no sense to progress any further
without some substantial, empirical measurements and good technical
explanations behind the observations.

>> These kinds of arguments lead to leftpad like situations, where people
>> defer any slightly complicated functionality to a library.  The last
>> thing I want to see when installing a package is that it drags along
>> dozens or even hundreds of recursive dependants, causing me to loose an
>> overview of what I have installed and what is being installed.  Every
>> dependency a package brings with it (especially packages like dash &
>> co.) is an argument against using it, imo.
>
> I don't think the leftpad situation (which I had to look up) can
> happen on GNU ELPA.  Even if, despite the FSF's precautions, something
> had to be removed, I'm sure there would be plenty of warning.

The point isn't so much that something gets removed (as you say, ELPA
plays the middle-man here by mirroring the repository contents), but
rather that a downstream bug or even a malicious change in a deep
dependency can cause much more harm, even if the inherent utility,
ie. need for the package in the first place was not that significant in
the first place.

> Lynn

Re: [GNU ELPA] New package: tam

[Adam Porter]

Hi Lynn,

This looks like a very interesting package.  My only feedback is 
trivial: that the names of the functions could omit "table" from their 
names, because it would make them more concise; and since they all 
operate on tables, it doesn't seem necessary for their names to specify 
that.

So, e.g., instead of:

;;  (tam-create-table N) => table of size N
;;  (tam-table-fullp TABLE) => nil unless TABLE is full
;;  (tam-table-emptyp TABLE) => nil unless TABLE is empty
;;  (tam-table-size TABLE) => number of slots in TABLE
;;  (tam-table-used TABLE) => number of slots of TABLE in use
;;  (tam-table-get TABLE IDX) => contents of TABLE slot at index IDX
;;  (tam-allocate TABLE OBJ) =>
;;      if not full, assigns OBJ to contents of a free slot in TABLE,
;;                   and returns the index of the slot
;;      if full, returns nil
;;  (tam-free TABLE INDEX) =>
;;      if slot at INDEX of TABLE is in use, move to the free list and
;;              return the object formerly held by the slot
;;      if slot is already free, signal an error
;;  (tam-table-free-list TABLE) => list of free indices in TABLE
;;  (tam-table-live-list TABLE) => list of in-use indices in TABLE

It could be:

;;  (tam-create N) => table of size N
;;  (tam-fullp TABLE) => nil unless TABLE is full
;;  (tam-emptyp TABLE) => nil unless TABLE is empty
;;  (tam-size TABLE) => number of slots in TABLE
;;  (tam-used TABLE) => number of slots of TABLE in use
;;  (tam-get TABLE IDX) => contents of TABLE slot at index IDX
;;  (tam-allocate TABLE OBJ) =>
;;      if not full, assigns OBJ to contents of a free slot in TABLE,
;;                   and returns the index of the slot
;;      if full, returns nil
;;  (tam-free TABLE INDEX) =>
;;      if slot at INDEX of TABLE is in use, move to the free list and
;;              return the object formerly held by the slot
;;      if slot is already free, signal an error
;;  (tam-free-list TABLE) => list of free indices in TABLE
;;  (tam-live-list TABLE) => list of in-use indices in TABLE

That 6-fewer-characters could sometimes make the difference between a 
form fitting on one line or two.  :)

Thanks for this contribution.

Adam

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Mon, Sep 18, 2023 at 3:26 PM Adam Porter <adam@alphapapa.net> wrote:
>
> Hi Lynn,
>
> This looks like a very interesting package.  My only feedback is
> trivial: that the names of the functions could omit "table" from their
> names, because it would make them more concise; and since they all
> operate on tables, it doesn't seem necessary for their names to specify
> that.
>
Thanks for taking a look.  The reason is that I was thinking about
adding functionality for pools of preallocated objects that leverage
the tables for tracking which objects are actually being used.  I went
ahead and wrote some basic support for such pools in the latest
version pushed.

It's possible the two data structures (tables and pools) could be
unified, but I want the tables to be able to track arbitrary data
associated with some nominal limited resource - the slots are
preallocated, but any other associated data is not.  For the scheduler
example, I may allow 24 simultaneous async processes to run, but I
could construct hundreds or thousands of job specifications that are
waiting to get scheduled.  I might use the pool object to pre-allocate
some largish number of those to avoid any allocation in a process
sentinel.

Of course, this introduces the possibility of use-after-free and using
unallocated objects (they are represented by simple indexes), so this
structure should only be used with appropriate caution.

Lynn

Re: [GNU ELPA] New package: tam

[Adam Porter]

Hi Lynn,

On 9/19/23 10:48, Lynn Winebarger wrote:

> Thanks for taking a look.  The reason is that I was thinking about
> adding functionality for pools of preallocated objects that leverage
> the tables for tracking which objects are actually being used.  I went
> ahead and wrote some basic support for such pools in the latest
> version pushed.

Of course, I should have known that you're several steps ahead of me. 
Forgive the noise.  :)  Looking forward to trying the library soon!

--Adam

Re: [GNU ELPA] New package: tam

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > Thanks for taking a look.  The reason is that I was thinking about
  > adding functionality for pools of preallocated objects that leverage
  > the tables for tracking which objects are actually being used.

I don't have much of a picture of what you're using this for.
For all I know, maybe it is a good method for that use.

But it does seem un-lispy.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: [GNU ELPA] New package: tam

[Adam Porter]

On 9/21/23 15:26, Richard Stallman wrote:

>    > Thanks for taking a look.  The reason is that I was thinking about
>    > adding functionality for pools of preallocated objects that leverage
>    > the tables for tracking which objects are actually being used.
> 
> I don't have much of a picture of what you're using this for.
> For all I know, maybe it is a good method for that use.
> 
> But it does seem un-lispy.

Agreed.  I am interested in it, but I'd like to know more about what 
problem it's intended to solve.  e.g. I've had functions that certainly 
do allocation and GC in a process sentinel, and AFAIK that hasn't been a 
problem.  But a project I'm working on may exercise this kind of 
functionality more in the future, so maybe tam.el could be helpful.

Re: [GNU ELPA] New package: tam

[Stefan Monnier]

Any reason why you're not using `cl-defstruct`?
Also, is it important to document that the values returned from
`tam-allocate` (and passed to `tam-free/tam-table-get`) are integers?


        Stefan

Re: [GNU ELPA] New package: tam

[Lynn Winebarger]

On Wed, Sep 20, 2023 at 12:07 PM Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> Any reason why you're not using `cl-defstruct`?
See my last response to Philip Kaludercic.

> Also, is it important to document that the values returned from
> `tam-allocate` (and passed to `tam-free/tam-table-get`) are integers?

I'm only committed to those functions returning an "index" that can be
created in constant time.  Since there is no facility for multiple
return values without some kind of consing, that pretty much means a
fixnum. I have at least considered making the integer return value
into a bitfield split between a slot number and some kind of
"generation number" recorded in each slot, so free-after-free errors
with an intervening reallocation could be caught.  That would be
over-engineering at this point, but I wouldn't commit to never
providing it as an option.

Maybe I should rename tam-table-get to just tam-get now that the table
and pool structures overlap.

Lynn