dgit.raspbian.org Git - git-annex.git/blob

   1 [[!comment format=mdwn
   2  username="joey"
   3  subject="""comment 32"""
   4  date="2021-06-14T20:26:52Z"
   5  content="""
   6 Some thoughts leading to a workable plan:
   7
   8 It's easy to detect this edge case because getAssociatedFiles will be
   9 returning a long list of files. So it could detect say 10 files in the list
  10 and start doing something other than the usual, without bothering the usual
  11 case with any extra work.
  12
  13 A bloom filter could be used to keep track of keys that have already had
  14 their associated files populated, and be used to skip the work the next
  15 time that same key is added. In the false positive case, it would check the
  16 associated files as it does now, so no harm done.
  17
  18 Putting these together, a bloom filter with a large enough capacity could
  19 be set up when it detects the problem, and used to skip the redundant work.
  20 This would change the checking overhead from `O(N^2)` to O(N^F)` where F is
  21 the false positive rate of the bloom filter. And the false positive rate of
  22 the usual git-annex bloom filter is small: 1/1000000 when half a million
  23 files are in it. Since 1-10 million files is where git gets too slow to be
  24 usable, the false positive rate should remain low up until the point other
  25 performance becomes a problem.
  26
  27 It would make sense to do this not only in populateUnlockedFiles but in
  28 Annex.Content.moveAnnex and Annex.Content.removeAnnex. Although removeAnnex
  29 would need a different bloom filter, since a file might have been populated
  30 and then somehow get removed in the same git-annex call.
  31 """]]