Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

HashMap.set keeps the old value when the new one is Equal to it

Chiusa
  • Qualcosa non va?
#9,535 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Una pull request collegata è già stata integrata.

  • #9536 di @schutzelaars — integrata

Valutazione

Difficoltà
3/5
Tempo stimato
1-2 giorni
Idoneità per principianti
58/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
typescript
Ambito
backend

Direzione di ricerca

Start with packages/effect/src/internal/hashMap.ts, especially LeafNode.set and CollisionNode.set, where the issue identifies the value equality checks. Read the existing HashMap tests and add coverage for overwriting with an equal value, including the reported User case; done means the new value is stored and overwrites avoid hashing or comparing the old value.

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

Descrizione

What steps can reproduce the bug?

When HashMap.set is given a key that is already in the map, it compares the new value with the stored one using Equal.equals (LeafNode.set, CollisionNode.set). If they are equal, it keeps the old value and returns the same map. A value whose Equal compares only some of its fields therefore loses the update:

class User {
  constructor(id, name) { this.id = id; this.name = name }
  [Equal.symbol](that) { return that instanceof User && that.id === this.id }
  [Hash.symbol]() { return Hash.string(this.id) }
}
let users = HashMap.make(["u1", new User("u1", "Ada")])
users = HashMap.set(users, "u1", new User("u1", "Grace"))
HashMap.getUnsafe(users, "u1").name // "Ada"

BigDecimal shows it too: setting BigDecimal.fromStringUnsafe("1.00") over BigDecimal.fromStringUnsafe("1") keeps the value with scale 0.

The check also makes every overwrite expensive. For object values set hashes the new value and compares it structurally with the old one before it replaces it. modify, modifyAt, union, setMany and mutate all go through set. The only ways around it are removing the key first, or marking values with Equal.byReference, which also changes how those values compare everywhere else and does not fix the lost update.

The script below shows the lost update, then overwrites each of 1,000 keys with a fresh plain object 200 times and measures time and allocation per set, and counts how often values are hashed during 1,000 overwrites of one key. I ran it three times on Node 26.8.1 with [email protected]; the same code is on main at 4cddd3c.

npm install [email protected]
node --expose-gc hashMapSet.mjs
hashMapSet.mjs 
// node --expose-gc hashMapSet.mjs
import v8 from "node:v8"
import { Equal, Hash, HashMap } from "effect"

// 1. A value whose Equal compares only its id loses the update.
class User {
  constructor(id, name) { this.id = id; this.name = name }
  [Equal.symbol](that) { return that instanceof User && that.id === this.id }
  [Hash.symbol]() { return Hash.string(this.id) }
}
let users = HashMap.make(["u1", new User("u1", "Ada")])
users = HashMap.set(users, "u1", new User("u1", "Grace"))
console.log(`name after set: ${HashMap.getUnsafe(users, "u1").name}`)

// 2. Overwriting every key with a fresh plain object, the way an immutable state update does.
const keys = 1_000
const rounds = 200
const allocatedBytes = () => v8.getHeapStatistics().total_allocated_bytes

const overwrite = (label, set) => {
  let map = HashMap.fromIterable(Array.from({ length: keys }, (_, key) => [key, { round: 0, key }]))
  for (let round = 0; round < 20; round++) {
    for (let key = 0; key < keys; key++) map = set(map, key, { round, key })
  }
  globalThis.gc()
  const bytesBefore = allocatedBytes()
  const start = performance.now()
  for (let round = 0; round < rounds; round++) {
    for (let key = 0; key < keys; key++) map = set(map, key, { round, key })
  }
  const nanos = ((performance.now() - start) * 1e6) / (rounds * keys)
  const bytes = (allocatedBytes() - bytesBefore) / (rounds * keys)
  console.log(`${label.padEnd(30)} ${nanos.toFixed(0).padStart(5)} ns/set ${bytes.toFixed(0).padStart(5)} bytes/set`)
}

overwrite("HashMap.set", (map, key, value) => HashMap.set(map, key, value))
overwrite("HashMap.remove + HashMap.set", (map, key, value) => HashMap.set(HashMap.remove(map, key), key, value))

// 3. How often set hashes a value it is about to replace.
let hashes = 0
class Counted {
  constructor(n) { this.n = n }
  [Equal.symbol](that) { return that instanceof Counted && that.n === this.n }
  [Hash.symbol]() { hashes++; return this.n }
}
let counted = HashMap.make(["a", new Counted(0)])
for (let n = 1; n <= 1_000; n++) counted = HashMap.set(counted, "a", new Counted(n))
console.log(`values hashed during 1000 overwrites: ${hashes}`)
What is the expected behavior?

set stores the value it is given. Overwriting a key costs about as much as inserting one, and does not hash or compare values.

What do you see instead?
name after set: Ada
HashMap.set                    575–626 ns/set  1766–1767 bytes/set
HashMap.remove + HashMap.set   128–157 ns/set  1783 bytes/set
values hashed during 1000 overwrites: 1001

The update is lost, and a plain set costs four times as much as removing the key and setting it again.

Additional information

The comparison came with the first Effect 4 HashMap (effect-smol#235), before plain objects became structurally equal by default (effect-smol#495). I found no test, doc or discussion that relies on set keeping an equal value. Effect 3's set always returned a new map: its node compared Option wrappers by reference (node.ts in [email protected]), and set passed a fresh Option.some(value).

Comparing with Object.is in both nodes fixes this, and keeps set returning the same map when the value is already stored, NaN included:

-      if (Equal_.equals(this.value, value)) {
+      if (Object.is(this.value, value)) {

-        if (Equal_.equals(this.entries[i][1], value)) {
+        if (Object.is(this.entries[i][1], value)) {

With that change the script prints:

name after set: Grace
HashMap.set                     84–89 ns/set   987–990 bytes/set
HashMap.remove + HashMap.set   135–156 ns/set  1775–1776 bytes/set
values hashed during 1000 overwrites: 0

Setting an equal copy then returns a new map, so code that skips work when a map keeps its identity, such as Atom's default equality, sees a change it did not see before. Map equality is unchanged. I have the fix with tests and a changeset and will open a PR.

I investigated this with an AI coding agent, Claude Code. The agent read the Effect sources, wrote the repro, and ran it. I reviewed the analysis before filing.

Lingua principale
TypeScript
Stelle
16.7k
Fork
808
Merge medio
12h 7m
PR unite (30g)
844

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

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 Effect-TS/effect

Tutte le issue di Effect-TS/effect

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.