perf: Replace std::list with std::vector in text layout#802
perf: Replace std::list with std::vector in text layout#802BlindBat wants to merge 1 commit intocrosspoint-reader:masterfrom
Conversation
Replace std::list with std::vector for the words, wordStyles, wordXpos, and wordContinues containers in TextBlock and ParsedText. Vectors provide contiguous memory layout for better cache locality and O(1) random access, eliminating per-node heap allocation and the 16-byte prev/next pointer overhead of doubly-linked list nodes. The indexed access also removes the need for a separate continuesVec copy that was previously built from the list for O(1) layout access.
|
Thanks @BlindBat! Did you verify the render time reduction on the real device? (Serial logs show exact ms for rendering.) |
|
@Uri-Tauber will do. Converting the PR to a draft until the performance tests are done (it requires time because the tests are semi-manual). |
| std::list<bool> lineContinues; | ||
| lineContinues.splice(lineContinues.begin(), wordContinues, wordContinues.begin(), wordContinuesEndIt); | ||
| // Build line data by moving from the original vectors using index range | ||
| std::vector<std::string> lineWords(std::make_move_iterator(words.begin() + lastBreakAt), |
There was a problem hiding this comment.
This was the missing piece I couldn't quite figure out when writing the original implementation. I wanted to use vectors, but didn't know about move iterators, so didn't know I could move items without needing to double allocate. That's basically the only reason I was using list, just to use splice.
znelson
left a comment
znelson
left a comment
There was a problem hiding this comment.
This change makes sense to me, and I've been using it for a while on device with no issues.
daveallie
left a comment
daveallie
left a comment
There was a problem hiding this comment.
In testing, there are some issues here. Notably, we are never clearing the empty nodes from the words and wordStyles vectors onces the items are moved, so they only ever grow. This is a problem as we check self->currentTextBlock->size() > 750 (where currentTextBlock->size() is just words.size()) in ChapterHtmlSlimParser to call self->currentTextBlock->layoutAndExtractLines early.
For paragraphs with over 750 words (e.g. I have been using Intermezzo as a test book which has several 800-1000 word paragraphs), this is problematic. Near the end of the paragraph layoutAndExtractLines gets called very frequently, slowing down indexing.
## Summary _Revision to @BlindBat's #802. Description comes from the original PR._ - Replace `std::list` with `std::vector` for word storage in `TextBlock` and `ParsedText` - Use index-based access (`words[i]`) instead of iterator advancement (`std::advance(it, n)`) - Remove the separate `continuesVec` copy that was built from `wordContinues` for O(1) access — now unnecessary since `std::vector<bool>` already provides O(1) indexing ## Why `std::list` allocates each node individually on the heap with 16 bytes of prev/next pointer overhead per node. For text layout with many small words, this means: - Scattered heap allocations instead of contiguous memory - Poor cache locality during iteration (each node can be anywhere in memory) - Per-node malloc/free overhead during construction and destruction `std::vector` stores elements contiguously, giving better cache performance during the tight rendering and layout loops. The `extractLine` function also benefits: list splice was O(1) but required maintaining three parallel iterators, while vector range construction with move iterators is simpler and still efficient for the small line-sized chunks involved. ## Files changed - `lib/Epub/Epub/blocks/TextBlock.h` / `.cpp` - `lib/Epub/Epub/ParsedText.h` / `.cpp` ## AI Usage YES ## Test plan - [ ] Open an EPUB with mixed formatting (bold, italic, underline) — verify text renders correctly - [ ] Open a book with justified text — verify word spacing is correct - [ ] Open a book with hyphenation enabled — verify words break correctly at hyphens - [ ] Navigate through pages rapidly — verify no rendering glitches or crashes - [ ] Open a book with long paragraphs — verify text layout matches pre-change behavior --------- Co-authored-by: Kuanysh Bekkulov <[email protected]>
|
Merged from updated #1038, closing this PR. |
4 participants
Summary
std::listwithstd::vectorfor word storage inTextBlockandParsedTextwords[i]) instead of iterator advancement (std::advance(it, n))continuesVeccopy that was built fromwordContinuesfor O(1) access — now unnecessary sincestd::vector<bool>already provides O(1) indexingWhy
std::listallocates each node individually on the heap with 16 bytes of prev/next pointer overhead per node. For text layout with many small words, this means:std::vectorstores elements contiguously, giving better cache performance during the tight rendering and layout loops. TheextractLinefunction also benefits: list splice was O(1) but required maintaining three parallel iterators, while vector range construction with move iterators is simpler and still efficient for the small line-sized chunks involved.Files changed
lib/Epub/Epub/blocks/TextBlock.h/.cpplib/Epub/Epub/ParsedText.h/.cppAI Usage
YES
Test plan