4 ms·

Variable length keys are difficult to implement efficiently. The alternative is not doing file name lookups by key query which would damage performance in unpat

Variable length keys are difficult to implement efficiently. The alternative is not doing file name lookups by key query which would damage performance in unpatholgical cases.

ajross 14y ago
Really? I'm not sure I buy that. B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound. That's just not going to be sensitive to the handful of cycles you save except in the case of tiny directories that are already in L1/L2 cache. But there, you're paying the up-front cost of hashing the input file name as "extra" and it's not even clear to me you'd save anything overall. Basically, this just smells like a premature optimization to me. If it were my project and lacked the hashing feature, and someone wanted to add it, I'd really want to see some numbers before accepting it.
- Someone 14y ago
  "B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound." I am not an expert on file systems, but have you thought about the following: - using file names in disk blocks rather than file name hashes means fewer entries per disk block. That, in turn, changes the constant of your B-tree traversal. - with variable-length keys, keeping your B-trees balanced is tricky, if not practically impossible. EDIT: disadvantage of using hashes would be that you need to read the filename proper (with small hashes, you cannot ignore hash collisions). That would be an extra I/O. So I guess this would not be beneficial for small directories. Maybe you could start out by having in-block hashes amd filenames and only move the names to a separate block when you need a second block?
  - cokernel_hacker 14y ago
    The most common implementation technique that I know of is to include a small constant number (~4) bytes of the actual name next to the hash.
    - Someone 14y ago
      I can see how that would help if your filenames are bin, dev, opt, usr, and var, but in the general case, I do not see how that beats having a longer hash (or a second, independent hash). Four bytes of the name will have less entropy than such data, and having part of the filename around will not help making sure that a matching hash implies a matching filename. Can you give explain this or give a name of a filesystem doing this?

Variable length keys are difficult to implement efficiently. The alternative is not doing file name lookups by key query which would damage performance in unpatholgical cases.

ajross 14y ago

Really? I'm not sure I buy that. B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound. That's just not going to be sensitive to the handful of cycles you save except in the case of tiny directories that are already in L1/L2 cache. But there, you're paying the up-front cost of hashing the input file name as "extra" and it's not even clear to me you'd save anything overall. Basically, this just smells like a premature optimization to me. If it were my project and lacked the hashing feature, and someone wanted to add it, I'd really want to see some numbers before accepting it.

Someone 14y ago
"B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound." I am not an expert on file systems, but have you thought about the following: - using file names in disk blocks rather than file name hashes means fewer entries per disk block. That, in turn, changes the constant of your B-tree traversal. - with variable-length keys, keeping your B-trees balanced is tricky, if not practically impossible. EDIT: disadvantage of using hashes would be that you need to read the filename proper (with small hashes, you cannot ignore hash collisions). That would be an extra I/O. So I guess this would not be beneficial for small directories. Maybe you could start out by having in-block hashes amd filenames and only move the names to a separate block when you need a second block?
- cokernel_hacker 14y ago
  The most common implementation technique that I know of is to include a small constant number (~4) bytes of the actual name next to the hash.
  - Someone 14y ago
    I can see how that would help if your filenames are bin, dev, opt, usr, and var, but in the general case, I do not see how that beats having a longer hash (or a second, independent hash). Four bytes of the name will have less entropy than such data, and having part of the filename around will not help making sure that a matching hash implies a matching filename. Can you give explain this or give a name of a filesystem doing this?