Feature #5248: Faster PStore

I agree with your points except following one. Masaki Matsushita wrote: > * check-sum calculation by String#sum > > As stated above, Present PStore calculates checksum of database file by Digest::MD5.digest to judge whether it should modify file or not. > However, Digest::MD5.digest is cryptographic hash function and I think it is too strong to use as a mere check sum. > Therefore, I modified PStore to use not Digest::MD5.digest but String#sum. When the checksum of your data accidentally equals to old data, PStore won't save the data and you lose it.

Yui NARUSE wrote: > When the checksum of your data accidentally equals to old data, PStore won't save the data and you lose it. The accident you mentioned seems to occur in the current implementation probabilistically. It will lead troublesome bugs. I believe it should be fixed.

Kenta Murata wrote: > Yui NARUSE wrote: > > When the checksum of your data accidentally equals to old data, PStore won't save the data and you lose it. > > The accident you mentioned seems to occur in the current implementation probabilistically. > It will lead troublesome bugs. I believe it should be fixed. I think it is OK until the probability is enough small and can't be attacked.

Kenta Murata wrote: > The accident you mentioned seems to occur in the current implementation probabilistically. As long as PStore uses any check sums or any cryptographic hash functions, there is possibility of collision. To avoid such bugs, it is needed to compare the whole data or to write data in every time.

• File patch.diff added

I wrote a patch using Digest::MD5.digest instead of String#sum. I think it is enough to avoid collision.

Matsushita-san, would you please split the patch into 2 parts, one for perf optimizations and another for trivial cosmetic changes? There's no pstore.rb maintainer now but I think I can understand perf fixes and merge it for actual pstore.rb users like you.

• File perf.diff added
• File cosmetic.diff added

Yes. I split the patch.

Thanks! perf.diff looks OK to me. I'm evaluating this. cosmetic.diff would be handled later.

require 'pstore'
require 'benchmark'

def run(size)
  file = "pstore_#{size}"
  File.unlink(file) if File.exist?(file)
  store = PStore.new(file)
  store.transaction do
    store["hoge"] = "hoge" * size
  end
  1000.times do
    store.transaction do
      store["hoge"] += "hoge"
    end
  end
end

Benchmark.bm(6) do |bm|
  [1000, 10000, 100000].each do |size|
    bm.report(size.to_s) { run(size) }
  end
end

So far, file truncation tweak is the key.

Original:

#            user     system      total        real
1000     0.120000   0.230000   0.350000 (  0.481725)
10000    0.260000   0.350000   0.610000 (  0.705170)
100000   3.500000   1.840000   5.340000 ( 18.753409)

With truncation tweak:

#            user     system      total        real
1000     0.080000   0.030000   0.110000 (  0.110230)
10000    0.300000   0.010000   0.310000 (  0.307720)
100000   2.230000   0.480000   2.710000 (  2.715860)

With deferred MD5 calculation:

#            user     system      total        real
1000     0.050000   0.230000   0.280000 (  0.417151)
10000    0.120000   0.410000   0.530000 (  0.804206)
100000   2.460000   1.750000   4.210000 ( 18.411857)

With both (full patch):

#            user     system      total        real
1000     0.070000   0.040000   0.110000 (  0.112234)
10000    0.180000   0.050000   0.230000 (  0.235963)
100000   1.490000   0.480000   1.970000 (  1.963404)

I'll merge it tonight.

• Assignee set to nahi (Hiroshi Nakamura)

Nice performance tweak :)

• Status changed from Open to Assigned

• Status changed from Assigned to Closed

Applied to trunk at r34083 (perf.diff) and r34084 (cosmetic.diff), excluding $0 -> $PROGRAM_NAME change because other libs are using $0. I'm closing this as 'fixed'. Thanks for the patch! We needed your eyes, I even didn't know we have that unnecessary 'marshal_dump_supports_canonical_option?' method in it...

Masaki Matsushita wrote: > Kenta Murata wrote: > > The accident you mentioned seems to occur in the current implementation probabilistically. > > As long as PStore uses any check sums or any cryptographic hash functions, there is possibility of collision. > To avoid such bugs, it is needed to compare the whole data or to write data in every time. About such possibility, see http://www.radiumsoftware.com/0406.html#040630

Thank you, Nakamura-san. I'm glad pstore.rb became faster. Yui NARUSE wrote: > About such possibility, see http://www.radiumsoftware.com/0406.html#040630 Thank you for letting me know.