freenode/#sicl - IRC Chatlog
Search
11:20:10
beach
No, the total number of existing elements, plus the new accumulated ones will give the estimate.
11:21:03
no-defun-allowed
Ah right. Don't we resize the adjustable vector with accumulated objects using a similar scheme to the hash table?
11:21:12
beach
I should put a meter in the Cleavir code so that we can see how many nodes are typically processed.
11:21:48
beach
Yes, that's what I meant by the adjustable vector being a problem. But at least no probing is required.
11:35:18
no-defun-allowed
Well, when you insert the elements at the end of measurement, you still probe as well.
12:36:41
heisig
Speaking of hash tables - I always wondered why hash tables with less than about 15 elements aren't implemented as an alist.
12:37:24
heisig
I occasionally write my own hash table wrapper that does exactly that, and it is measurably faster in many cases.
13:37:12
pjb
heisig: note the actual threshold count is implementation and platform dependent (and of course, also dependent on the test and hash functions (not sxhash!)). You would need to benchmark it at the start of the program.
13:37:58
pjb
heisig: I've measured as low as 5 elements with sbcl and as high as 35 elements with clisp, on the platform where I tested it.
14:05:08
Bike
for the record the hash table growth thing isn't so much a problem in clasp any more. BIR has some higher structure that makes it traversable without consing.
14:07:14
Bike
and ASTs have an actual tree structure now, so you don't need to maintain a seen table.
14:07:45
Bike
(the only cases ASTs weren't trees had to do with lexical variables and blocks - nothing too fundamental)
14:48:13
beach
The average size for an invocation is just 73 nodes. But then, I also have many small source files.
14:48:19
Bike
there's not an exactly analogous operation to m-i-a-o. but the way traversals work now is just following "next" slots, so overhead is pretty low.
14:48:42
Bike
10% of execution time even with no inlining sounds like it could end up being problematic.
14:49:54
Bike
in more detail, how it works in BIR is that reverse postorder is computed and cached in the nodes, so iteration just needs to go through it. so traversal doesn't cons, and it also allows multiple traversals to go simultaneously (unlike if there was a mark slot in the node)
14:51:04
beach
Sounds good. But that order has to be computed once, right? And then maintained for every graph modification?
14:54:35
Bike
it can also be fully recomputed if there's some extensive modification. since the graph is traversed more often than modified, even doing a consing recomputation on modifications instead of traverses is still helpful for performance.
14:59:26
Bike
haven't been using meters much since external profiling has been working pretty well for us, but i could add them back in