4 ms·
> Because we have to process hundreds of gigabytes of art assets to build game packages, we wanted a fast, non-cryptographic hash for use in change detection an
by kazinator 5y ago
> Because we have to process hundreds of gigabytes of art assets to build game packages, we wanted a fast, non-cryptographic hash for use in change detection and deduplication. We had been using a cryptographic hash (SHA-1), but it was unnecessarily slowing things down.
That's because you were doing a potentially silly thing: hashing every byte.
What does a hash tell you? If two hashes are different, it confirms that the objects are different. If two hashes are the same, they could be the same object or they could be different.
For that purpose, you don't have to hash everything: just hash the areas where objects are likely to differ.
If two 15 gigabyte files are likely to have differences in their first kilobyte, then hashing just first kilobyte (negligibly fast) will work just as well as hashing 15 gigabytes.
If two files are of different length, then they are not the same. How about:
hash(<length> + <first kilobyte> + <last kilobyte>)
For deduplication, a 32 bit CRC could probably be reasonably efficient. No matter what hash you use, you have to verify the collisions. If CRC32 is enough to make false positives rare over your type of data set, it's good enough.
- cb321 5y agoThis is roughly how https://github.com/c-blake/cligen/blob/master/examples/dups.nim https://github.com/c-blake/cligen/blob/master/examples/dups.... can work. There is little question that changing the scale of the problem very much lessons performance sensitivity to the hash.
- andruc 5y ago"just hash the areas where objects are likely to differ" Correct me if I'm wrong but given these are art assets, wouldn't "determining where the objects are likely to differ" itself be an expensive/hard problem?
- daemin 5y agoOnce you need to load any parts of a file into memory you might as well compute the hash for all the bytes that you've loaded into memory. The act of loading the bytes from permanent storage (even NVME SSD) is likely to be many orders of magnitude slower than actually computing the hash. So it makes no sense to just "hash parts of the file" when in all likelihood the entire file will be getting loaded into memory even if you actively read only a few bytes from each 4k block.
- cb321 5y agoIt really depends. The early bytes probably contain things like image dimensions which might discriminate a lot - or not at all. They might contain palette-style color information which might discriminate tons - or not at all. Most things with hash functions depend upon distributions of inputs relative to the function, though. I think it would be accurate to say "Determining where they are likely to differ is not necessarily hard, but it could be." If it happens to be easy then you can radically change the scale of the problem. File length alone is a weak hash actively maintained by any file system and so available "for free" (or one stat call). And it can work surprisingly well, as the grandparent alludes to. EDIT: You actually do not need to even open(2) files that are not part of "same size clusters", never mind hash their data. This alone can really squash the problem size over a more naive approach even if you did feel the need to hash the whole file. EDIT: And in terms of performance, if this data has to actually be read off a drive then the hash need not go any faster than the drive IO which is probably much, much slower than most candidate hash functions. Even PCIe5.0 NVMes are only like 14 GB/s, SATA buses like 0.75 GB/s, etc.
- DeathArrow 5y agoFinding sections of the file where data can be different is not only potentially hard but depends on the type of data. So can't be made generic. Comparing files based on size is trivial and I presume people will always do it first before attempting to use a hash or even CRC. As you say, single disk read speeds are slow but there is a high chance they will improve over time. PCIe 6.0 x16 has a bandwidth of 128 GB/s. It would be theoretically possible to reach that aggregate speed in raid 0.
- cb321 5y ago>Finding sections of the file where data can be different is not only potentially hard but depends on the type of data. So can't be made generic I agree, and a cousin comment of mine suggests user-specifiable sampling which can always be a full sample in the "hard case". Often, once one has identified true duplicate candidates, a full compare is desirable to not trust any hash, and that full compare uses a lot of IO. That depends on the user, too. >Comparing files based on size is trivial and I presume people will always do it first before attempting to use a hash or even CRC. It is unclear the meow guys did this since they seemed to motivate hash performance based on dedup and they unlikely had IO > 10GB/s in 2018, but it's hard to know for sure.
- pepoluan 5y agoCRC32 is actually very slow in modern CPUs. So if you can use an algorithm that is both (1) faster and (2) better quality, why not use that algo instead?
- kazinator 5y ago> CRC32 is actually very slow in modern CPUs Dd you read my whole comment? If we are hashing just a few kilobytes of a multi-gigabyte file, it almost certainly doesn't matter.
- midnightclubbed 5y agoI wouldn't categorize it as 'very slow', at worse 50% slower than 128bit XXH3 hash (and faster than the 32bit XXH hash). Modern intel processors have the CRC32C instructions and ARM have both CRC32 and CRC32C. There is a reluctance in some of the hash comparisons to use the hardware CRC implementations for compatibility reasons, but most modern CPUs have them. The main argument for using a hardware CRC32 (and to some extent a software one too) is simplicity. If your use-case needs decent (but not blinding) performance, then there is something to be said for a hash implementation that can be written in ~10 lines of code. You still have to handle the possibility of collisions but any 32bit hash has that restriction, which is fine for many uses.