about summary refs log tree commit diff
path: root/tvix/nix-compat/src/store_path
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2023-03-30T22·19+0300
committertazjin <tazjin@tvl.su>2023-03-31T16·46+0000
commitce502bdc892e2f8f24ac2babe96791542b0bbec3 (patch)
tree30f95780e463b7598f7bee7ea278045ab34f3788 /tvix/nix-compat/src/store_path
parent5bf913432424ad29e976f4acad535aa1340d84fe (diff)
refactor(tvix/eval): improve representation of chunk/span mapping r/6066
This switches out the previous compressed representation (count of
instructions per span) with a representation where the chunk's span
list stores the index of the first operation that belongs to a span,
and finds the right span by using a binary search when looking them
up.

This improves the lookup complexity from O(n) to O(log n).

This improvement was suggested and (mostly) implemented by GPT-4. I
only fixed up some names and updated the logic for deleting
spans (which it only did not do because I didn't tell it about that).

The code was verified by producing a complex error before/after the
change and ensuring that all spans in the error match exactly.

Co-Authored-By: GPT-4
Change-Id: Ibfa12cc6973af1c9b0ae55bb464d1975209771f5
Reviewed-on: https://cl.tvl.fyi/c/depot/+/8385
Reviewed-by: ezemtsov <eugene.zemtsov@gmail.com>
Tested-by: BuildkiteCI
Autosubmit: tazjin <tazjin@tvl.su>
Diffstat (limited to 'tvix/nix-compat/src/store_path')
0 files changed, 0 insertions, 0 deletions