5 ms·

Instead of addition, why not use an actual hashing algorithm, truncated to a certain number of bits? That'll give you better binning and give you flexibility ab

Instead of addition, why not use an actual hashing algorithm, truncated to a certain number of bits? That'll give you better binning and give you flexibility about filesize / number of file tradeoffs. I like the idea of using unicode characters -- have you performance tested it to see if it gives superior performance to an ASCII filename of the same number of bytes?

peterburkimsher 8y ago
Binning! That's the word, not "hash distribution" like I wrote. Yes, I'd like to experiment more with different hashing algorithms. It needs to run fast on the query side. Unicode seems great, but I noticed that filenames are restricted on various platforms, including Github. Uppercase and lowercase URLs are equivalent. So perhaps I should consider a different subset of characters instead of the first 65536 Unicode characters. Performance is much faster than grep, because it only reads a fraction of the file. I couldn't find a good benchmark for ElasticSearch/Lucene/Sphinx, and apparently there isn't an easy way to compare. https://stackoverflow.com/questions/44846271/performance-comparison-elasticsearch-vs-solr-vs-sphinx-vs-whoosh https://stackoverflow.com/questions/44846271/performance-com...
- sonofgod 8y ago
  Whilst there's a few hashing algorithms explicitly designed to be memory and time-intensive to make password retrieval impractical, most are really fast, even in Javascript. (Given there's g and so should be fine but isn't particularly lightweight. oing to be network access, I expect it to be entirely negligible) In terms of performance I was more wondering whether or not "£" (one code point, two bytes) was much less expensive than "Ao" (two code points, two bytes). Just restricting yourself to ASCII might also have advantages for ensuring portability. https://qntm.org/safe https://qntm.org/safe might also be of interest: discusses potential issues with using unicode as a high-density encoding -- base-2048 is Twitter-safe.
nine_k 8y ago
Making a longer hash than 2 bytes would help selectivity, and filesystems are usually very good at finding files by name. Also, apparently the files are not sorted by name (or I failed to see it). Searching in a sorted file using binary search is logarithmic, much faster than grepping which is linear. Sorting can be done once, when the files are formed. BTW inserting into a sorted file should also be pretty fast (cheaper than appending and re-sorting).
- peterburkimsher 8y ago
  The data is in the order it came in from OSMNames. http://osmnames.org/download/ http://osmnames.org/download/ When there's two elements with the same name (e.g. Geneva), the first result is the most common (the city I was born, not the town in the US).
netgusto 8y ago
I proposed to use a simple polynomial hash https://github.com/peterburk/pagefish/issues/1 https://github.com/peterburk/pagefish/issues/1

peterburkimsher 8y ago

Binning! That's the word, not "hash distribution" like I wrote. Yes, I'd like to experiment more with different hashing algorithms. It needs to run fast on the query side. Unicode seems great, but I noticed that filenames are restricted on various platforms, including Github. Uppercase and lowercase URLs are equivalent. So perhaps I should consider a different subset of characters instead of the first 65536 Unicode characters. Performance is much faster than grep, because it only reads a fraction of the file. I couldn't find a good benchmark for ElasticSearch/Lucene/Sphinx, and apparently there isn't an easy way to compare. https://stackoverflow.com/questions/44846271/performance-comparison-elasticsearch-vs-solr-vs-sphinx-vs-whoosh https://stackoverflow.com/questions/44846271/performance-com...

sonofgod 8y ago
Whilst there's a few hashing algorithms explicitly designed to be memory and time-intensive to make password retrieval impractical, most are really fast, even in Javascript. (Given there's g and so should be fine but isn't particularly lightweight. oing to be network access, I expect it to be entirely negligible) In terms of performance I was more wondering whether or not "£" (one code point, two bytes) was much less expensive than "Ao" (two code points, two bytes). Just restricting yourself to ASCII might also have advantages for ensuring portability. https://qntm.org/safe https://qntm.org/safe might also be of interest: discusses potential issues with using unicode as a high-density encoding -- base-2048 is Twitter-safe.

nine_k 8y ago

Making a longer hash than 2 bytes would help selectivity, and filesystems are usually very good at finding files by name. Also, apparently the files are not sorted by name (or I failed to see it). Searching in a sorted file using binary search is logarithmic, much faster than grepping which is linear. Sorting can be done once, when the files are formed. BTW inserting into a sorted file should also be pretty fast (cheaper than appending and re-sorting).

peterburkimsher 8y ago
The data is in the order it came in from OSMNames. http://osmnames.org/download/ http://osmnames.org/download/ When there's two elements with the same name (e.g. Geneva), the first result is the most common (the city I was born, not the town in the US).

netgusto 8y ago

I proposed to use a simple polynomial hash https://github.com/peterburk/pagefish/issues/1 https://github.com/peterburk/pagefish/issues/1