On Tuesday, November 5, 2013 15:59:56 Derek wrote:
Aaron J. Seigo <aseigo <at> kde.org> writes:
There is no page index. Variable length pages without an accompanying index means that it is not possible to seek directly to a given page; however given the relatively small size of the IDS, the small number of pages and that the headers allow skipping from page to page this is deemed acceptable.
Would you please educate me (and others may be interested) why to not use an index? Do we expect pages to be added frequently, requiring rewriting an index (and thus shifting all contents)? Do we expect that people will get it wrong? Is the initialization environment so constrained that it cannot even use an index?
indexes mostly make sense when there is lots of data and/or random access is common. my operational assumption here is that the # of pages will remain small (100s at most; i expect most EEPROMs to have 2) and random access on the storage is inexpensive.
if a process expects to do lots of random page accesses, an index can always be generated in main memory by processing the the page headers once at runtime.
in theory all the page headers could be banged right to the front of the EEPROM after the DIDS header and serve as a lookup table without taking any more storage space on the EEPROM. that does mean that if any page changes, you have to rewrite the entire EEPROM (rather than just from the changed page on), but we can probably assume that writes are rare and so this doesn’t really matter.
i simply doubted that having all the page indexes separate from the page data would result in any meaningful real world performance gains, whereas with an index you have to read the entire index and keep the whole thing in memory to traverse to any page to have any benefit. (incrementally reading the index is the same as page headers with page data, given constant speed reads, and since this isn’t a spinning disk that’s a reasonable assumption). writing similarly becomes slightly more complex, though certainly still easy enough that nobody should get it wrong ...
it just didn’t seem worth it and so i stuck to simplicity. ime unless you can justify gains, complexity is to be avoided. it piles up quicker than one might expect. (<insert ramblings about premature optimizations here>)
that said, once there is something akin to consensus on the DIDS i’ll definitely make sure this gets tested for performance. if it makes a difference to store an index of some sort on the EEPROM rather than traverse page-to- page, we can always adjust the spec.