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

Aperta
  • Qualcosa non va?
#2,346 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
c
Ambito
backend-api-design

Direzione di ricerca

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.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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

Lingua principale
C
Stelle
3
Fork
7
Merge medio
6h 32m
PR unite (30g)
285

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di InauguralSystems/EigenScript

Tutte le issue di InauguralSystems/EigenScript

Issue simili

Altre issue su C

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.