Does the heap-allocated nature of the recursive structure slow it down?

[sezna]

Some research and benchmarking is needed here. The nodes are defined as an Option<Box> which may or may not have perf impacts.

[Ameobea]

If it turns out that heap allocation is causing perf issues, you may want to check out slab allocation: https://docs.rs/slab/0.4.2/slab/ It is pretty much just a `Vec` under the hood, but it provides a nice API on top that returns "pointer"-like indices into the slab and supports an allocate/free-like interface. It avoids a lot of the allocation overhead that comes from bookkeeping and synchronization and stuff while still letting you create new nodes or whatever it is you're allocating easily. It also gives you "pointers" which are smaller than 64 bytes (better for cache) as well as putting all of your nodes closer together in memory (also good for cache).

…

On Wed, Jan 22, 2020 at 4:18 PM Alex Hansen ***@***.***> wrote: Some research and benchmarking is needed here. The nodes are defined as an Option<Box> which may or may not have perf impacts. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#32?email_source=notifications&email_token=ABBCR2NISFESTMNCZINXQZLQ7DO5BA5CNFSM4KKOXQAKYY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IIDMN7Q>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABBCR2OSOCOLLXDPJ226HFTQ7DO5BANCNFSM4KKOXQAA> .

[sezna]

Thanks @Ameobea. This looks very promising, as I do indeed allocate a lot of memory for just one data type. Can't wait to benchmark this :)