seekKeyCached supports only string target arg

staltz commented 2 years ago

Context: https://github.com/ssb-ngi-pointer/jitdb/pull/209#issuecomment-1087482324

I opted to remove support for buffer target and keep only string target because:

We can't have strings as keys in WeakMap (because strings don't get deallocated)
We shouldn't have buffers as keys in Map (because it would retain these buffers from being GCd)
The string target is anyway converted only once when seekKeyCached calls seekKey

For the record, perf bench:

Generating JSON structure...
Structure generated in 26ms
operation, ops/ms
BIPF.encode 1.9179133103183736
JSON.stringify 4.557885141294439
BIPF.decode 7.1022727272727275
JSON.parse 5.408328826392645
JSON.parse(buffer) 5.537098560354374
JSON.stringify(JSON.parse()) 3.114294612270321
BIPF.seek(string) 285.7142857142857
BIPF.seek2(encoded) 555.5555555555555
BIPF.seek(buffer) 909.0909090909091
BIPF.seekCached(buffer) 1428.5714285714287
BIPF.seekPath(encoded) 500
BIPF.seekPath(compiled) 666.6666666666666
BIPF.compare() 344.82758620689657

staltz commented 2 years ago

Given that this is a follow up PR, I think it's rather safe to not issue a breaking change, and just bump minor instead.

staltz commented 2 years ago

There could be a performance problem here if converting from string to buffer isn't cheap. Because for each different record, we would do the conversion 'value' => Buffer.from('value').

I could add another cache for these conversions though. What do you think?

arj03 commented 2 years ago

Might be best to benchmark :)

staltz commented 2 years ago

Well, here are some results.

Benchmark before `targetBuf` cache

const cache1 = new WeakMap()

function seekKeyCached(buffer, start, target) {
  let cache2 = cache1.get(buffer)
  if (!cache2) cache1.set(buffer, (cache2 = new Map()))
  let cache3 = cache2.get(start)
  if (!cache3) cache2.set(start, (cache3 = new Map()))
  if (typeof target !== 'string') throw new Error('x')
  if (cache3.has(target)) {
    return cache3.get(target)
  } else {
    const result = seekKey(buffer, start, target)
    cache3.set(target, result)
    return result
  }
}

BIPF.seek(buffer) 1111.111111111111
BIPF.seekCached(buffer) 1666.6666666666667
...
BIPF.seek(uniqueMsg) 1111.111111111111
BIPF.seekCached(uniqueMsg) 1666.6666666666667

Benchmark after `targetBuf` cache

const cache1 = new WeakMap()
const targetCache = new Map()

function seekKeyCached(buffer, start, target) {
  let cache2 = cache1.get(buffer)
  if (!cache2) cache1.set(buffer, (cache2 = new Map()))
  let cache3 = cache2.get(start)
  if (!cache3) cache2.set(start, (cache3 = new Map()))
  if (typeof target !== 'string') throw new Error('x')
  let targetBuf = targetCache.get(target)
  if (!targetBuf) {
    targetBuf = Buffer.from(target)
    targetCache.set(target, targetBuf)
  }
  if (cache3.has(target)) {
    return cache3.get(target)
  } else {
    const result = seekKey(buffer, start, targetBuf)
    cache3.set(target, result)
    return result
  }
}

BIPF.seek(buffer) 1000
BIPF.seekCached(buffer) 1666.6666666666667
...
BIPF.seek(uniqueMsg) 1000
BIPF.seekCached(uniqueMsg) 1428.5714285714287

staltz commented 2 years ago

Yeah, seems like targetBuf cache doesn't help. This PR is ready for review @arj03

ssbc / bipf