3 ms·
Nice library with many features. But I do not always understand the focus on memory usage. I guess that the reason behind this is that less memory allocations,
by fjfaase 3y ago
Nice library with many features. But I do not always understand the focus on memory usage. I guess that the reason behind this is that less memory allocations, have a positive effect on execution times. In a parser, where you often have to compare identifiers, it is a good idea to put all strings for identifiers into a unique pointer with the help of a hash table.
In my interpreting parser [1] I use a hexa hash tree [2] for storing identifiers. It is not very memory efficient, but very fast. It turns every string (from the input buffer) into a unique pointer for that string pointing to a copy of the string. In this way comparing string (identifiers) is equivalent to comparing pointers.
The idea of the hexa hash tree is that is a tree where each node has sixteen child nodes. Which node is selected is based on a step wise evaluated hash function that first takes the lower four bytes of successive characters in the string, and after reaching the end of the string, the higher four bytes of the characters. The nodes often taken up more memory space than the strings themselves.
[1] https://github.com/FransFaase/IParse/ https://github.com/FransFaase/IParse/
[2] https://github.com/FransFaase/IParse/blob/master/software/Ident.cpp https://github.com/FransFaase/IParse/blob/master/software/Id...
- Sharlin 3y agoNot just allocations, but critically – especially on modern machines – cache coherency. Indirections are an enemy of performance, and indirections to many different parts of memory in particular. A custom allocator can be a great help though, especially in a compiler where you can pretty much just use a fast slab/bump allocator and not worry about freeing memory until the end.
- TazeTSchnitzel 3y agoDo you mean cache locality? Coherence is not something ordinary single-threaded code has to be concerned with.
- Sharlin 3y agoOops, indeed, brain fart.
- dgb23 3y agoWe have terms and languages to express computational complexity, algorithms, temporal logic etc. But what about data logistics and CPU mechanics? How good are we at expressing things like memory fragmentation, cache locality, throughput and latency of operations etc? All of these things affect how the machine operates in very real ways, to a degree that often trumps the higher level mathematical concepts above. I only ever see these things explained in high-level, heuristic terms, observed as a black box or spelled out literally as code. Is there a language based on how the CPU and memory work that I'm not aware of?
- fjfaase 3y agoI do not think that such a language has been developed. The complexity of how a CPU, with several levels of caching, RAM, harddrives (with their own caching), and network storage (with their own caching) is simply mind boggling. For that reason, I think that this route is not often taken. I guess that whenever modeling of execution is performed it is done to analyse the behaviour of an existing implementation in order to find ways to improve it. If there is someone who has made an attempt to do something in this direction, I think it is Donald E. Knuth in his 'The Art of Computer Programming'. I think, for example about section 5.4 'External sorting' in Volume 3 'Sorting and Searching' [1]. [1] https://seriouscomputerist.atariverse.com/media/pdf/book/Art%20of%20Computer%20Programming%20-%20Volume%203%20(Sorting%20&%20Searching).pdf https://seriouscomputerist.atariverse.com/media/pdf/book/Art...
- IshKebab 3y agoHeap memory allocation can be very slow. Reducing the number of allocations is often a fantastic way to get very significant speed ups. Using an integer to identify strings is very common in parsers - it's called "string interning".