IRC channel logs
2025-01-26.log
back to list of logs
<ttz`>rlb: hi! a follow-up on my study of functional mappings in Guile since you were interested to know were fash was standing. So from my understanding, fash is just an implementation of a HAMT with three different "modes" for the nodes. Some documentation would be welcome since the code looks quite messy. Last time I achieved really close performances using a B-tree, which has the nice feature of allowing in-order iteration (while a HAMT <ttz`>does not). Today, I implemented a HAMT that is faster than fash. <sneek>ttz`, ArneBab says: thank you for the benchmarking! I always love reliable data like this! Is there a chance you could get a few datapoints in-between and check the big-O scaling for the different datastructures? The base runtime (for some reasonable size of inputs) and the big-O complexity for the different datastructures would be wonderful to have in a table in the guile reference manual. <ttz`>ArneBab: sure, I can do that, I was already planning do some more work on graphs: as you say, it would be nice to get a visual feeling of the asymptotic complexity <ttz`>That's what I tried initially, but could get scatter plots to use sensible colors and point size so the graphs were rather hard to read. <ttz`>Big-O complexities are well-studied, I can summary them in a table in the README. <rlb>ttz: thanks, and yeah, I'd figured out the HAMT bit and had been poking at the code a little, though not seriously. <ttz>If you are interested, I will push some updated timing soon. Today I have worked on a reliable way to micro-benchmark my data-structures. I realized how hard it is to take into account both the JIT and the GC. <ttz>But I now I have somewhat reproducible results with a precision to the tenth of nanosecond, so I am happy with it. <rlb>Right -- those costs are distributed over time, depending on the implementations, but are of course part of the overall cost. e.g. the jvm selectively jitting code depending on how "hot" it is, etc. <ttz>Yes, I have read some interesting blog posts related to benching on the JVM <ttz>I followed their advices <ttz>So on my machine, my HAMT performs a get in about 140ns (without match) and 180ns (with match), while fash 180ns (without match) and 240ns (with match). <ttz>For reference, the hash-table performs a get in about 70ns without or without match. <ttz>So these are all pretty good results. <ttz>(all these timings are for mappings containing 32 bindings) <ttz>The difference between the two HAMT implementations tends to decrease as the number of bindings increases. Maybe fash is asymptotically faster, for 1M bindings they are on-par. <ttz>My HAMT seems to be reliably faster for insertion though. <rlb>Interesting -- though I tend to favor larger-scale tests, say replacing the subsystem in some bigger benchmark (or "real" problem) and seeing how it performs wrt memory and cpu. But of course tests on both ends are useful/needed if you're really trying to optimize. <rlb>And also, for scheme, in this case, I imagine any number of things might take some work to a adapt, since they may have been written to use mutable maps... <rlb>But yeah, all interesting. <ttz>yes sure, micro-benchmarks are what they are. But I had no "larger scale" benchmarks to run :) <ttz>I particular, I really don't know how to benchmark memory usage. <ttz>If you have hints, I would thankfully take them <rlb>Right - when testing the utf8 branch a while back, iirc I tried ecraven's tree and lokke's "make check", but that's not broad, and I didn't actually look much at memory. And of course, I didn't have to rework any of the tests the way you would if you were trying to check the things you're currently investigating. <rlb>Regarding memory -- that's not easy, and harder, depending on what you want to know and the implementation/platform. i.e. does the platform (guile, the jvm, etc.) give memory back, and are you looking for intermediate results or just a "high water mark", and "many other things". <ttz>well I really am not knowledgeable regarding this topic... the best I tried was to observe top while running the benches, but I realized that it really doesn't give much input <rlb>You could, for example, periodically graph rss over time on an otherwise idle machine for some job, but that's still only telling you whatever rss means with your current kernel and kernel's behaviors. Or maybe the platform provides more detailed allocation stats (not sure if we do?). <rlb>It's a potential rabbit hole :) <rlb>basically "how many pages does the process have 'in ram <rlb>You can see git, for example have a *giant* (hundreds of mb) memory footprint for large repos, but nearly all of that isn't actually in ram -- it's mmapped packfiles and indexes, and it shows up as vss (virtual set size). The rss is related to how many of the pages of those files git has actually "touched" recently. <rlb>I've assumed I'll probably mess with perf more at some point. <rlb>If I had to guess, I'd guess that whippet has notable introspection facilities. <ttz>that would be really great <ttz>In other scheme, it is possible to know how much bytes were allocated, is it possible for Guile? <rlb>That's what I was wondering above wrt "(not sure if we do?)". <ttz>mmh apparently there is a (gc-stats) procedure <rlb>And don't know about other schemes, but of course something like kawa has all the jvm's instrumentation underneath... <ttz>yeah, that's what's need in sharing the same runtime as big languages