No string search from an offset: a linear scanner must split or slice (found in #2344)

Đang mở
  • Có gì không ổn?
#2,346 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
c
Lĩnh vực
backend-api-design

Hướng nghiên cứu

Start with index_of and string handling in the interpreter, then read lib/template.eigs render and the linked #2345 benchmarks. Define and test the start-position behavior, including byte offsets inside multibyte characters and both strict modes; compare timings at two sizes. Update docs/SPEC.md, docs/llms.txt, API output, and a changelog fragment, then verify the old-versus-new render cases and four delimiter benchmarks.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

area:stdlib enhancement

What is missing. index_of of [haystack, needle] always searches from the start of the string. There is no way to ask for the first match at or after a position. A scanner that walks a string therefore has two choices: cut the rest of the string off at each step, which copies it each time and is quadratic over the string, or split the whole string on the delimiter and stitch the pieces back together.

Minimal repro

s is "a{{b{{c"
print of (index_of of [s, "{{"])
print of (index_of of [s, "{{", 2])

The first call prints 1. The second raises index_of: expected a fixed-shape list with at most 2 elements. There is no call that returns 4, the second match, without slicing s.

Where it was found. #2344 and its fix #2345, in lib/template.eigs render. The old render sliced, and was quadratic in the number of placeholders: 30 seconds at 200,001. The new one splits on {{ and }}. It is linear, but a template dense with delimiters that do not pair up now costs interpreted work for each of them, where the old code skipped them in native code. At 100,000 delimiters the four shapes measured take 161 to 299 ms, against 0.3 to 0.6 ms on main (the table under "What it costs" in #2345's description). A search that starts at an offset would let render scan natively and stay linear.

Indexes are bytes today: for "é{{b", index_of gives 2 and len gives 5.

Done when

  • A string search can start at a position: either a third argument to index_of or a new builtin, decided in the pull request with the reason. It returns the index of the first match at or after the start, in the unit index_of returns today, and -1 when there is none.
  • A start that is negative, past the end, not an integer, or inside a multi-byte character has a stated behaviour, with a test for each. A haystack or needle that is not a string raises, in the default mode and with EIGS_STRICT=0.
  • It does not copy the haystack: n searches over a string of n bytes with n matches run in time linear in n, shown by timings at two sizes.
  • docs/SPEC.md, docs/llms.txt and eigenscript --api show it, and a changelog fragment is added.
  • lib/template.eigs render uses it: the exhaustive old-against-new test of #2345 still passes, and the four shapes of #2345's "What it costs" are within noise of main at 100,000 delimiters. If the pull request grows large, split this box into its own issue and link it here.

Found while fixing #2344; out of that change's scope, so it is filed and not worked around.

— Claude DevBox

Ngôn ngữ chính
C
Star
3
Fork
7
Merge trung bình
6 giờ 32 phút
Pull request đã merge (30 ngày)
285

Chuẩn bị môi trường

Mở trong Codespaces

Khởi chạy dev container của dự án ngay trên trình duyệt, bằng tài khoản GitHub của bạn.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của InauguralSystems/EigenScript

Tất cả issue của InauguralSystems/EigenScript

Issue tương tự

Thêm issue về C

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.