inkcpp
inkcpp copied to clipboard
Optimisation: Replace linear searches with binary searches for more consistent performance.
In a middle-sized story in a release build, I was seeing good performance at one end (100us or so per getline) vs. bad performance at the other end (300us). This change puts getline under 100us for the entire story.
- Define file format with C/C++ structs rather than code.
- Describe file sections in header so we don't need to scan the whole thing on load.
- Remove vestiges of Endian-swapping and make read_list_flag a free function.
- Bump format version.
- Fix UTF-8 test (needed to use prefix)
- Rename compiler's _containers stream to _instructions since that's what it stores.
- Remove iterate_containers, add find_container_for, find_container_id, container_data and container_offset.
- Implement find_container_for and find_offset_for with upper_bound.
- Store expanded information about containers (container_data) including tree structure.
- Rewrite jump using new toolkit - update ip, unwind stack, then generate new stack with search/tree walk.
- Move little bit of container entry logic out of globals_impl::visit.
NB: This might be too much change? My 2p is that the speed improvements are worthwhile and the changes to the file format get it into a better shape which is more clearly defined and easier to extend.
I spotted more avenues for optimisation but trying not to get too distracted by them :)