Macaulay2 / Macaulay2/M2

join could derive a list's hash code from its inputs instead of refolding the whole list

Open
#4,589 0 comments 0 reactions 0 assignees View on GitHub
bugs directory Interpreter
Dominant language
Macaulay2
Stars
435
Forks
297
Avg merge
4d 20h
Merged PRs (30d)
11

Description

This issue was triaged from [`bugs/dan/1-join-hash`](https://github.com/Macaulay2/M2/blob/388c1ff0ce30d83751dea7bc7eac77fdc1305dd7/bugs/dan/1-join-hash), one of the 857 files removed from the pre-GitHub `bugs/` tree by [`d2c8d27826`](https://github.com/Macaulay2/M2/commit/d2c8d27826) and catalogued in [#36](https://github.com/Macaulay2/M2/issues/36). **The commentary below was written by Claude (Claude Opus 5, via Claude Code)**, not by @d-torrance, whose account posted it -- please weigh it accordingly.

### The original file, verbatim

```text
join(List,List) has to compute new hash codes by scanning the new list,
presumably. Perhaps it could save time by computing the answer from the
previous hash codes.

Similarly for new List from List, toList, toSequence, etc.
```

### Where it stands today

The guess in the file is right, and the saving is worth having.

### Every List construction folds the whole list

`basic.d:114-117` does `r.hash = hash(r)`, and `hash(x:List)` at `:82-85` is an element-by-element fold
with multiplier `1299833` over the seed `x.Class.hash + 23407`.

### Measured

| | time |
| --- | ---: |
| `join` of two 200k lists | 11.2 ms |
| the identical fold over the resulting 400k elements | 7.5–8.5 ms |
| reading a List's stored hash | 0.69 µs |

The fold is measurable separately because a `Sequence`'s hash is **not** cached — `basic.d:33-36` refolds
on every call. So roughly two-thirds of `join` is hashing.

### And the fold is combinable

```
h(L ++ M) = 1299833^(#M) * (hash L - c) + hash M (mod 2^64), c = hash class L + 23407
```

verified on seven cases including both empty sides, mixed element types and nested lists. That replaces
an O(n) fold with one modular exponentiation.

A caution from getting it wrong first: my initial derivation used the *Sequence* constants
`seqHashSeed`/`seqHashMult` (`basic.d:8-9`) and failed all five test cases. The List fold uses different
constants.

### The file's second half is already moot

`new List from J` and `toSequence J` on 400k elements cost 1–2 µs, because a List wraps a Sequence and
they share the array.

### Fix site

`d/actors4.d:1175-1186`, plus a `list()` variant in `basic.d` taking a precomputed hash.

`open` · disposition `issue` · source of truth: [`bug-triage/catalog.tsv`](https://github.com/d-torrance/M2/blob/bug-triage/bug-triage/catalog.tsv)

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with d/actors4.d:1175-1186 and the list() variant in basic.d. Read basic.d:82-85 and 114-117 to confirm the List hash constants and construction path, then check the documented join formula against the existing empty, mixed-type, and nested-list cases. Done means join derives the resulting hash without refolding all elements while preserving the existing hash values.

Written by the indexing model from the issue text.

Assessment

Domain
backend, performance
Issue type
Feature
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
64/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.