make freed op re-use closer to O(1)

previously freed ops were stored as one singly linked list, and
a failed search for a free op to re-use could potentially search
that entire list, making freed op lookups O(number of freed ops),
or given that the number of freed ops is roughly proportional to
program size, making the total cost of freed op handling roughly
O((program size)**2).  This was bad.

This change makes opslab_freed into an array of linked list heads,
one per op size.  Since in a practical sense the number of op sizes
should remain small, and insertion is amortized O(1), this makes
freed op management now roughly O(program size).

fixes #17555

1 files changed, 2 insertions, 1 deletions

diff --git a/op.h b/op.h
index cbb19d557a..4c086a5cc6 100644
--- a/op.h
+++ b/op.h
@@ -703,8 +703,9 @@ struct opslot {
 struct opslab {
     OPSLAB *	opslab_next;		/* next slab */
     OPSLAB *	opslab_head;		/* first slab in chain */
-    OP *	opslab_freed;		/* chain of freed ops (head only)*/
+    OP **	opslab_freed;		/* array of sized chains of freed ops (head only)*/
     size_t	opslab_refcnt;		/* number of ops (head slab only) */
+    U16         opslab_freed_size;      /* allocated size of opslab_freed */
     U16		opslab_size;		/* size of slab in pointers,
                                            including header */
     U16         opslab_free_space;	/* space available in this slab