3 ms·

Great questions! A Hex Fiend document is represented in-memory as a list of slices of files and memory buffers. The b+tree is just an optimization on top of the

Great questions! A Hex Fiend document is represented in-memory as a list of slices of files and memory buffers. The b+tree is just an optimization on top of the list, and is not written to disk. For example, say the user opens file1, which is 100 bytes. Our document starts off with one slice: (file1, 0, 100) Now the user scrolls to offset 75 and types 30 bytes. This splits the original slice at offset 75, so our new list is: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100) The user may also open file2, copy part of it, and paste it at the end of the document. Now the document references two files: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100), (file2, 200, 300) So there's no real dependence on the original file: a document may reference arbitrarily many files (until it's saved). By organizing the list as a b+tree, it's fast to find the slice at a given byte offset in the document. Hex Fiend does not use mmap because I wanted to support 4+GB files in 32 bit mode. But error handling with mmap is miserable, so I think it is wise to avoid mmap even in 64 bit.

anyfoo 6y ago
I'm surprised you don't mention insertion/deletion for why plain mmap (without chunk lists or trees) does not work... isn't that a deal breaker regardless, or am I missing something? EDIT: Ah, did you just mean why it doesn't use mmap at all, e.g. backing the actual data in the tree?
- ridiculous_fish 6y ago
  Yep. A simple no-insertion editor could just mmap a file with in-place editing. But you could support insertions by weaving together the mmap'd buffer with other buffers. This is how the suckless vis editor works: https://lists.suckless.org/dev/1409/23497.html https://lists.suckless.org/dev/1409/23497.html The advantage is that your document can be a simple list of (ptr, length) pairs. The price you pay is error handling: mmap reports errors through raising SIGSEGV or SIGBUS, which are very painful to handle properly.
  - anyfoo 6y ago
    Ah, yes. That would indeed still be a chunk list, albeit one backed by mmap. I can of course be totally wrong, but I think the OP was wondering why you couldn't simply mmap the entire file in place without managing any lists, trees, or any data structure except for a flat array representing the whole file.
  - waynesonfire 6y ago
    Yes, a document can just be a (ptr, length). I guess I don't see the benefit a b-tree adds here. I'd probably just use a red-black, AVL, even binary tree with nodes either pointing to blocks on the file (ptr, length) or nodes containing new data in memory (ptr, length, data) with the invariant that no two nodes can ever have overlapping (ptr, length). My understand is that btrees are a multi-level index that reduces the number of blocks that need to be read from disk to manage an index. I don't see that being a use-case here and thought maybe I was missing something. With that said, I wonder if the calculus changes if the file is so large that it won't fit in memory and thus, b-trees maybe somehow helpful in flushing data to disk. However, this then starts to look like a block allocator problem. Suppose as you run out of memory you start flushing blocks to disk. But the user is still editing the file and so some of these blocks that were flushed to disk are no longer valid. Youu'd hve to keep track of those "unallocated" blocks on disk to enable re-use thus improve space efficiency. As far as I understand, block allocators are not solved with btrees.
deleted 6y ago
[deleted]

anyfoo 6y ago

I'm surprised you don't mention insertion/deletion for why plain mmap (without chunk lists or trees) does not work... isn't that a deal breaker regardless, or am I missing something? EDIT: Ah, did you just mean why it doesn't use mmap at all, e.g. backing the actual data in the tree?

ridiculous_fish 6y ago
Yep. A simple no-insertion editor could just mmap a file with in-place editing. But you could support insertions by weaving together the mmap'd buffer with other buffers. This is how the suckless vis editor works: https://lists.suckless.org/dev/1409/23497.html https://lists.suckless.org/dev/1409/23497.html The advantage is that your document can be a simple list of (ptr, length) pairs. The price you pay is error handling: mmap reports errors through raising SIGSEGV or SIGBUS, which are very painful to handle properly.
- anyfoo 6y ago
  Ah, yes. That would indeed still be a chunk list, albeit one backed by mmap. I can of course be totally wrong, but I think the OP was wondering why you couldn't simply mmap the entire file in place without managing any lists, trees, or any data structure except for a flat array representing the whole file.
- waynesonfire 6y ago
  Yes, a document can just be a (ptr, length). I guess I don't see the benefit a b-tree adds here. I'd probably just use a red-black, AVL, even binary tree with nodes either pointing to blocks on the file (ptr, length) or nodes containing new data in memory (ptr, length, data) with the invariant that no two nodes can ever have overlapping (ptr, length). My understand is that btrees are a multi-level index that reduces the number of blocks that need to be read from disk to manage an index. I don't see that being a use-case here and thought maybe I was missing something. With that said, I wonder if the calculus changes if the file is so large that it won't fit in memory and thus, b-trees maybe somehow helpful in flushing data to disk. However, this then starts to look like a block allocator problem. Suppose as you run out of memory you start flushing blocks to disk. But the user is still editing the file and so some of these blocks that were flushed to disk are no longer valid. Youu'd hve to keep track of those "unallocated" blocks on disk to enable re-use thus improve space efficiency. As far as I understand, block allocators are not solved with btrees.

deleted 6y ago

[deleted]