inkcpp icon indicating copy to clipboard operation
inkcpp copied to clipboard

Optimisation: Replace linear searches with binary searches for more consistent performance.

Open willvale opened this issue 1 month ago • 1 comments

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 :)

willvale avatar Dec 23 '25 08:12 willvale