diff options
author | Vincent Ambo <mail@tazj.in> | 2023-03-30T22·19+0300 |
---|---|---|
committer | tazjin <tazjin@tvl.su> | 2023-03-31T16·46+0000 |
commit | ce502bdc892e2f8f24ac2babe96791542b0bbec3 (patch) | |
tree | 30f95780e463b7598f7bee7ea278045ab34f3788 /ops | |
parent | 5bf913432424ad29e976f4acad535aa1340d84fe (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 'ops')
0 files changed, 0 insertions, 0 deletions