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

Offen
  • Stimmt etwas nicht?
#2,346 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
25/100
Issue-Typ
Feature
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
c
Bereich
backend-api-design

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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

Vorherrschende Sprache
C
Sterne
3
Forks
7
Ø Merge
6 Std. 32 Min.
Gemergte PRs (30 T.)
285

Entwicklungsumgebung

In Codespaces öffnen

Startet den Dev-Container des Projekts im Browser, mit Ihrem eigenen GitHub-Konto.

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus InauguralSystems/EigenScript

Alle Issues in InauguralSystems/EigenScript

Ähnliche Issues

Weitere Issues zu C

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.