anagram-finder/web

Fork 0

Cache anagram results, keyed on the dictionary contents #5

New issue

Closed

opened 2026-08-23 16:12:08 +02:00 by myrmidex · 1 comment

myrmidex commented

2026-08-23 16:12:08 +02:00

Owner

Context

Every search scans the full dictionary: 466,550 words, 4.6MB (core/assets/words.txt),
read line by line through Matcher::getWordList() and filtered four times per word. The same
anagram produces the same result every time, so repeat searches redo all of it.

Since results are deterministic given (anagram, minLength, dictionary), they cache cleanly.

Cache key

The requirement is that entries survive indefinitely but invalidate the moment the dictionary
changes. Three candidate fingerprints:

Approach	Verdict
`filemtime()`	No. The dictionary ships inside the Docker image; the mtime changes on every rebuild even when content is identical, so the cache would be dumped on each deploy for nothing.
`hash_file('xxh128', ...)`	Yes. Content-addressed — changes only when the words actually change. This is the honest answer to "as long as the file does not change".
Installed `anagram-finder/core` version	Cheap, but a proxy. Wrong if the file is swapped without a version bump.

Proposed key:

anagram:{dictHash}:{minLength}:{normalisedAnagram}

dictHash — hash_file('xxh128', ...) on the dictionary, itself cached (see below)
normalisedAnagram — lowercased and letter-sorted, so eamstoxil and latoximse
share one entry. Worth doing: the same bag of letters in any order is the same query.

Hashing 4.6MB costs a few ms, which would undo the saving if done per request. Cache the hash
under a key derived from filemtime + filesize — cheap stats that change whenever the file
is replaced, and a false hit there is impossible without an identical-size, identical-mtime
substitution.

Storage

CACHE_STORE is currently database (config/cache.php:18). That is fine and needs no new
service. Store entries forever() — the dictionary hash in the key is the invalidation
mechanism, so a TTL would only cause needless recomputation. Old entries from a superseded
dictionary become unreachable rather than stale; a cache:prune-stale-tags-style sweep or a
plain cache:clear on deploy handles the accumulation if it ever matters.

Scope

Wrap the Matcher::findWords() call in the controller, not inside core — caching is an
application concern, and core should stay dependency-free (it currently requires only
illuminate/collections)
Normalise the anagram (lowercase + sort letters) before both the lookup and the match call
Cache the dictionary hash separately, keyed on mtime+size
Add the dictionary path or hash as a public accessor on Matcher if needed — the constant
is currently private const DICTIONARY

Acceptance

Second identical search does not re-scan the dictionary
eamstoxil and latoximse hit the same cache entry
Replacing words.txt invalidates all entries without a manual flush
Rebuilding the image with an unchanged dictionary does not invalidate
Dictionary hash is not recomputed on every request

Note

Related: the [FIND WORDS] button is already disabled client-side when the input matches the
current result (resources/views/index.blade.php), but that is a UI guard only — a direct POST
still triggers a full scan. This ticket addresses the actual cost.

## Context Every search scans the full dictionary: **466,550 words, 4.6MB** (`core/assets/words.txt`), read line by line through `Matcher::getWordList()` and filtered four times per word. The same anagram produces the same result every time, so repeat searches redo all of it. Since results are deterministic given (anagram, minLength, dictionary), they cache cleanly. ## Cache key The requirement is that entries survive indefinitely but invalidate the moment the dictionary changes. Three candidate fingerprints: | Approach | Verdict | |---|---| | `filemtime()` | **No.** The dictionary ships inside the Docker image; the mtime changes on every rebuild even when content is identical, so the cache would be dumped on each deploy for nothing. | | `hash_file('xxh128', ...)` | **Yes.** Content-addressed — changes only when the words actually change. This is the honest answer to "as long as the file does not change". | | Installed `anagram-finder/core` version | Cheap, but a proxy. Wrong if the file is swapped without a version bump. | Proposed key: ``` anagram:{dictHash}:{minLength}:{normalisedAnagram} ``` - `dictHash` — `hash_file('xxh128', ...)` on the dictionary, itself cached (see below) - `normalisedAnagram` — lowercased and **letter-sorted**, so `eamstoxil` and `latoximse` share one entry. Worth doing: the same bag of letters in any order is the same query. Hashing 4.6MB costs a few ms, which would undo the saving if done per request. Cache the hash under a key derived from `filemtime` + `filesize` — cheap stats that change whenever the file is replaced, and a false *hit* there is impossible without an identical-size, identical-mtime substitution. ## Storage `CACHE_STORE` is currently `database` (`config/cache.php:18`). That is fine and needs no new service. Store entries `forever()` — the dictionary hash in the key is the invalidation mechanism, so a TTL would only cause needless recomputation. Old entries from a superseded dictionary become unreachable rather than stale; a `cache:prune-stale-tags`-style sweep or a plain `cache:clear` on deploy handles the accumulation if it ever matters. ## Scope - Wrap the `Matcher::findWords()` call in the controller, not inside `core` — caching is an application concern, and `core` should stay dependency-free (it currently requires only `illuminate/collections`) - Normalise the anagram (lowercase + sort letters) before both the lookup and the match call - Cache the dictionary hash separately, keyed on mtime+size - Add the dictionary path or hash as a public accessor on `Matcher` if needed — the constant is currently `private const DICTIONARY` ## Acceptance - [ ] Second identical search does not re-scan the dictionary - [ ] `eamstoxil` and `latoximse` hit the same cache entry - [ ] Replacing `words.txt` invalidates all entries without a manual flush - [ ] Rebuilding the image with an unchanged dictionary does **not** invalidate - [ ] Dictionary hash is not recomputed on every request ## Note Related: the `[FIND WORDS]` button is already disabled client-side when the input matches the current result (`resources/views/index.blade.php`), but that is a UI guard only — a direct POST still triggers a full scan. This ticket addresses the actual cost.

myrmidex added this to the v0.1.0 milestone 2026-08-23 16:12:08 +02:00

myrmidex added the

enhancement

label 2026-08-23 16:12:08 +02:00

myrmidex self-assigned this 2026-08-23 16:12:09 +02:00

myrmidex commented

2026-08-23 21:47:23 +02:00

Author

Owner

Done — `b11bcc3`

Measured: 386ms cold → 1ms warm on retinas (282 matches), identical results.

Cache key

anagram:{dictHash}:{minLength}:{sortedLetters} — e.g.
anagram:bf647cb5910ec9ea8d85efbf053daa2b:3:aeilmostx

hash_file('xxh128') on the dictionary rather than filemtime, as planned: the file ships
inside the image, so its mtime changes on every rebuild while the words do not.
The hash is itself cached under filemtime:filesize, so 4.6MB is not rehashed per request.
Letters sorted — verified that eamstoxil, latoximse and LATOXIMSE produce an identical
key and share one entry.
Entries stored forever; a replaced dictionary makes old keys unreachable rather than stale.

Caching lives in app/Services/AnagramSearch.php, not in core — core stays dependency-free
so tui can keep consuming it.

Validation, included per the scope decision

Two pre-existing bugs surfaced while testing, both fixed:

/find/EAMSTOXIL returned 0 matches — the dictionary is lowercase and Matcher::check
compares raw characters
/find/eam5t0xil accepted digits and scanned the dictionary anyway

Both routes now share one rule set (alpha:ascii, min:2, max:24), input is lowercased in
prepareForValidation, and invalid input redirects home with the message rendered in the
form's existing @error block, input repopulated. Verified: digits, single characters,
over-length strings and spaces all redirect rather than reaching the matcher.

Bug found in my own first attempt

Caching the Collection directly returned __PHP_Incomplete_Class from the database store and
500'd. Now caching plain arrays and rebuilding the Collection on the way out.

Not done

No tests. AnagramSearch is structured to be testable — key derivation and normalisation are
separable — but the ticket did not ask and web currently carries only starter-kit tests.
Worth its own ticket.

## Done — `b11bcc3` **Measured:** 386ms cold → **1ms warm** on `retinas` (282 matches), identical results. ### Cache key `anagram:{dictHash}:{minLength}:{sortedLetters}` — e.g. `anagram:bf647cb5910ec9ea8d85efbf053daa2b:3:aeilmostx` - `hash_file('xxh128')` on the dictionary rather than `filemtime`, as planned: the file ships inside the image, so its mtime changes on every rebuild while the words do not. - The hash is itself cached under `filemtime:filesize`, so 4.6MB is not rehashed per request. - Letters sorted — verified that `eamstoxil`, `latoximse` and `LATOXIMSE` produce an identical key and share one entry. - Entries stored `forever`; a replaced dictionary makes old keys unreachable rather than stale. Caching lives in `app/Services/AnagramSearch.php`, not in `core` — `core` stays dependency-free so `tui` can keep consuming it. ### Validation, included per the scope decision Two pre-existing bugs surfaced while testing, both fixed: - `/find/EAMSTOXIL` returned **0 matches** — the dictionary is lowercase and `Matcher::check` compares raw characters - `/find/eam5t0xil` accepted digits and scanned the dictionary anyway Both routes now share one rule set (`alpha:ascii`, `min:2`, `max:24`), input is lowercased in `prepareForValidation`, and invalid input redirects home with the message rendered in the form's existing `@error` block, input repopulated. Verified: digits, single characters, over-length strings and spaces all redirect rather than reaching the matcher. ### Bug found in my own first attempt Caching the `Collection` directly returned `__PHP_Incomplete_Class` from the database store and 500'd. Now caching plain arrays and rebuilding the Collection on the way out. ### Not done No tests. `AnagramSearch` is structured to be testable — key derivation and normalisation are separable — but the ticket did not ask and `web` currently carries only starter-kit tests. Worth its own ticket.

myrmidex closed this issue

2026-08-23 21:47:29 +02:00

No labels

bug

docs

enhancement

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: anagram-finder/web#5

No description provided.

Cache anagram results, keyed on the dictionary contents #5

Context

Cache key

Storage

Scope

Acceptance

Note

Done — b11bcc3

Cache key

Validation, included per the scope decision

Bug found in my own first attempt

Not done

Done — `b11bcc3`