Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
26
C++ takes long to compile There is more than one reason for it but one of the reasons is excessive re-parsing of the same .h header files. In SumatraPDF I’m using an extreme #include discipline to keep compilation times in check. The rule is simple: a .h file cannot #include other .h files. I didn’t come up with this idea, I got it from Rob Pike: http://doc.cat-v.org/bell_labs/pikestyle I’ve been following this rule for several years in SumatraPDF, a medium sized C++ project of over 100k loc. It works. “It works” is more important that it seems. Many ideas seem great on paper but fail in practice. Name an economically successful communist country. Don’t get me wrong: the price of minimizing compilation times is eternal vigilance. Writing C++ while following that rule is annoying. In code, things depend on other things. If a struct in foo.h depends on struct in bar.h a quick fix is to #include "bar.h" in foo.h. You do it once and it works Done once and for all: in your foo.c you just...
over a year ago

Improve your reading experience

Logged in users get linked directly to articles resulting in a better reading experience. Please login for free, it takes less than 1 minute.

More from Krzysztof Kowalczyk blog

All about Svelte 5 snippets

Snippets are a useful addition to Svelte 5. I use them in my Svelte 5 projects like Edna. Snippet basics A snippet is a function that renders html based on its arguments. Here’s how to define and use a snippet: {#snippet hello(name)} <div>Hello {name}!</div> {/snippet} {@render hello("Andrew")} {@render hello("Amy")} You can re-use snippets by exporting them: <script module> export { hello }; </script> {@snippet hello(name)}<div>Hello {name}!</div>{/snippet} Snippets use cases Snippets for less nesting Deeply nested html is hard to read. You can use snippets to extract some parts to make the structure clearer. For example, you can transform: <div> <div class="flex justify-end mt-2"> <button onclick={onclose} class="mr-4 px-4 py-1 border border-black hover:bg-gray-100" >Cancel</button > <button onclick={() => emitRename()} disabled={!canRename} class="px-4 py-1 border border-black hover:bg-gray-50 disabled:text-gray-400 disabled:border-gray-400 disabled:bg-white default:bg-slate-700" >Rename</button > </div> into: {#snippet buttonCancel()} <button onclick={onclose} class="mr-4 px-4 py-1 border border-black hover:bg-gray-100" >Cancel</button > {/snippet} {#snippet buttonRename()}...{/snippet} To make this easier to read: <div> <div class="flex justify-end mt-2"> {@render buttonCancel()} {@render buttonRename()} </div> </div> snippets replace default <slot/> In Svelte 4, if you wanted place some HTML inside the component, you used <slot />. Let’s say you have Overlay.svelte component used like this: <Overlay> <MyDialog></MyDialog> </Overlay> In Svelte 4, you would use <slot /> to render children: <div class="overlay-wrapper"> <slot /> </div> <slot /> would be replaced with <MyDialog></MyDialog>. In Svelte 5 <MyDialog></MyDialog> is passed to Overlay.svelte as children property so you would change Overlay.svelte to: <script> let { children } = $props(); </script> <div class="overlay-wrapper"> {@render children()} </div> children property is created by Svelte compiler so you should avoid naming your own props children. snippets replace named slots A component can have a default slot for rendering children and additional named slots. In Svelte 5 instead of named slots you pass snippets as props. An example of Dialog.svelte: <script> let { title, children } = $props(); </script> <div class="dialog"> <div class="title"> {@render title()} </div> {@render children()} </div> And use: {#snippet title()} <div class="fancy-title">My fancy title</div> {/snippet} <Dialog title={title}> <div>Body of the dialog</div> </Dialog> passing snippets as implicit props You can pass title snippet prop implicitly: <Dialog> {#snippet title()} <div class="fancy-title">My fancy title</div> {/snippet} <div>Body of the dialog</div> </Dialog> Because {snippet title()} is a child or <Dialog>, we don’t have to pass it as explicit title={title} prop. The compiler does it for us. snippets to reduce repetition Here’s part of how I render https://tools.arslexis.io/ {#snippet row(name, url, desc)} <tr> <td class="text-left align-top" ><a class="font-semibold whitespace-nowrap" href={url}>{name}</a> </td> <td class="pl-4 align-top">{@html desc}</td> </tr> {/snippet} {@render row("unzip", "/unzip/", "unzip a file in the browser")} {@render row("wc", "/wc/", "like <tt>wc</tt>, but in the browser")} It saves me copy & paste of the same HTML and makes the structure more readable. snippets for recursive rendering Sometimes you need to render a recursive structure, like nested menus or file tree. In Svelte 4 you could use <svelte:self> but the downside of that is that you create multiple instances of the component. That means that the state is also split among multiple instances. That makes it harder to implement functionality that requires a global view of the structure, like keyboard navigation. With snippets you can render things recursively in a single instance of the component. I used it to implement nested context menus. snippets to customize rendering Let’s say you’re building a Menu component. Each menu item is a <div> with some non-trivial children. To allow the client of Menu customize how items are rendered, you could provide props for things like colors, padding etc. or you could allow ultimate flexibility by accepting an optional menuitem prop that is a snippet that renders the item. You can think of it as a headless UI i.e. you provide the necessary structure and difficult logic like keyboard navigation etc. and allow the client lots of control over how things are rendered. snippets for library of icons Before snippets every SVG Icon I used was a Svelte component. Many icons means many files. Now I have a single Icons.svelte file, like: <script module> export { IconMenu, IconSettings }; </script> {#snippet IconMenu(arg1, arg2, ...)} <svg>... icon svg</svg> {/snippet}} {#snippet IconSettings()} <svg>... icon svg</svg> {/snippet}}

18 hours ago 2 votes
C++ engineering decision in SumatraPDF code

SumatraPDF is a medium size (120k+ loc, not counting dependencies) Windows GUI (win32) C++ code base started by me and written by mostly 2 people. The goals of SumatraPDF are to be: fast small packed with features and yet with thoughtfully minimal UI It’s not just a matter of pride in craftsmanship of writing code. I believe being fast and small are a big reason for SumatraPDF’s success. People notice when an app starts in an instant because that’s sadly not the norm in modern software. The engineering goals of SumatraPDF are: reliable (no crashes) fast compilation to enable fast iteration SumatraPDF has been successful achieving those objectives so I’m writing up my C++ implementation decisions. I know those decisions are controversial. Maybe not Terry Davis level of controversial but still. You probably won’t adopt them. Even if you wanted to, you probably couldn’t. There’s no way code like this would pass Google review. Not because it’s bad but becaues it’s different. Diverging from mainstream this much is only feasible if you have total control: it’s your company or your own open-source project. If my ideas were just like everyone else’s ideas, there would be little point in writing about them, would it? Use UTF8 strings internally My app only runs on Windows and a string native to Windows is WCHAR* where each character consumes 2 bytes. Despite that I mostly use char* assumed to be utf8-encoded. I only decided on that after lots of code was written so it was a refactoring oddysey that is still ongoing. My initial impetus was to be able to compile non-GUI parts under Linux and Mac. I abandoned that goal but I think that’s a good idea anyway. WCHAR* strings are 2x larger than char*. That’s more memory used which also makes the app slower. Binaries are bigger if string constants are WCHAR*. The implementation rule is simple: I only convert to WCHAR* when calling Windows API. When Windows API returns WCHA* I convert it to utf-8. No exceptions Do you want to hear a joke? “Zero-cost exceptions”. Throwing and catching exceptions generate bloated code. Exceptions are a non-local control flow that makes it hard to reason about program. Every memory allocation becomes a potential leak. But RAII, you protest. RAII is a “solution” to a problem created by exceptions. How about I don’t create the problem in the first place. Hard core #include discipline I wrote about it in depth. My objects are not shy I don’t bother with private and protected. struct is just class with guts exposed by default, so I use that. While intellectually I understand the reasoning behind hiding implementation details in practices it becomes busy work of typing noise and then even more typing when you change your mind about visibility. I’m the only person working on the code so I don’t need to force those of lesser intellect to write the code properly. My objects are shy At the same time I minimize what goes into a class, especially methods. The smaller the class, the faster the build. A common problem is adding too many methods to a class. You have a StrVec class for array of strings. A lesser programmer is tempted to add Join(const char* sep) method to StrVec. A wise programmer makes it a stand-alone function: Join(const StrVec& v, const char* sep). This is enabled by making everything in a class public. If you limit visibility you then have to use friendto allow Join() function access what it needs. Another example of “solution” to self-inflicted problems. Minimize #ifdef #ifdef is problematic because it creates code paths that I don’t always build. I provide arm64, intel 32-bit and 64-bit builds but typically only develop with 64-bit intel build. Every #ifdef that branches on architecture introduces potential for compilation error which I’ll only know about when my daily ci build fails. Consider 2 possible implementations of IsProcess64Bit(): Bad: bool IsProcess64Bit() { #ifdef _WIN64 return true; #else return false; #endif } Good: bool IsProcess64Bit() { return sizeof(uintptr_t) == 8; } The bad version has a bug: it was correct when I was only doing intel builds but became buggy when I added arm64 builds. This conflicts with the goal of smallest possible size but it’s worth it. Stress testing SumatraPDF supports a lot of very complex document and image formats. Complex format require complex code that is likely to have bugs. I also have lots of files in those formats. I’ve added stress testing functionality where I point SumatraPDF to a folder with files and tell it to render all of them. For greater coverage, I also simulate some of the possible UI actions users can take like searching, switching view modes etc. Crash reporting I wrote about it in depth. Heavy use of CrashIf() C/C++ programmers are familiar with assert() macro. CrashIf() is my version of that, tailored to my needs. The purpose of assert / CrashIf is to add checks to detect incorrect use of APIs or invalid states in the program. For example, if the code tries to access an element of an array at an invalid index (negative or larger than size of the array), it indicates a bug in the program. I want to be notified about such bugs both when I test SumatraPDF and when it runs on user’s computers. As the name implies, it’ll crash (by de-referencing null pointer) and therefore generate a crash report. It’s enabled in debug and pre-release builds but not in release builds. Release builds have many, many users so I worry about too many crash reports. premake to generate Visual Studio solution Visual Studio uses XML files as a list of files in the project and build format. The format is impossible to work with in a text editor so you have no choice but to use Visual Studio to edit the project / solution. To add a new file: find the right UI element, click here, click there, pick a file using file picker, click again. To change a compilation setting of a project or a file? Find the right UI element, click here, click there, type this, confirm that. You accidentally changed compilation settings of 1 file out of a hundred? Good luck figuring out which one. Go over all files in UI one by one. In other words: managing project files using Visual Studio UI is a nightmare. Premake is a solution. It’s a meta-build system. You define your build using lua scripts, which look like test configuration files. Premake then can generate Visual Studio projects, XCode project, makefiles etc. That’s the meta part. It was truly a life server on project with lots of files (SumatraPDF’s own are over 300, many times more for third party libraries). Using /analyze and cppcheck cppcheck and /analyze flag in cl.exe are tools to find bugs in C++ code via static analysis. They are like a C++ compiler but instead of generating code, they analyze control flow in a program to find potential programs. It’s a cheap way to find some bugs, so there’s no excuse to not run them from time to time on your code. Using asan builds Address Sanitizer (asan) is a compiler flag /fsanitize=address that instruments the code with checks for common memory-related bugs like using an object after freeing it, over-writing values on the stack, freeing an object twice, writing past allocated memory. The downside of this instrumentation is that the code is much slower due to overhead of instrumentation. I’ve created a project for release build with asan and run it occasionally, especially in stress test. Write for the debugger Programmers love to code golf i.e. put us much code on one line as possible. As if lines of code were expensive. Many would write: Bad: // ... return (char*)(start + offset); I write: Good: // ... char* s = (char*)(start + offset); return s; Why? Imagine you’re in a debugger stepping through a debug build of your code. The second version makes it trivial to set a breakpoint at return s line and look at the value of s. The first doesn’t. I don’t optimize for smallest number of lines of code but for how easy it is to inspect the state of the program in the debugger. In practice it means that I intentionally create intermediary variables like s in the example above. Do it yourself standard library I’m not using STL. Yes, I wrote my own string and vector class. There are several reasons for that. Historical reason When I started SumatraPDF over 15 years ago STL was crappy. Bad APIs Today STL is still crappy. STL implementations improved greatly but the APIs still suck. There’s no API to insert something in the middle of a string or a vector. I understand the intent of separation of data structures and algorithms but I’m a pragmatist and to my pragmatist eyes v.insert (v.begin(), myarray, myarray+3); is just stupid compared to v.inert(3, el). Code bloat STL is bloated. Heavy use of templates leads to lots of generated code i.e. surprisingly large binaries for supposedly low-level language. That bloat is invisible i.e. you won’t know unless you inspect generated binaries, which no one does. The bloat is out of my control. Even if I notice, I can’t fix STL classes. All I can do is to write my non-bloaty alternative, which is what I did. Slow compilation times Compilation of C code is not fast but it feels zippy compared to compilation of C++ code. Heavy use of templates is big part of it. STL implementations are over-templetized and need to provide all the C++ support code (operators, iterators etc.). As a pragmatist, I only implement the absolute minimum functionality I use in my code. I minimize use of templates. For example Str and WStr could be a single template but are 2 implementations. I don’t understand C++ I understand the subset of C++ I use but the whole of C++ is impossibly complicated. For example I’ve read a bunch about std::move() and I’m not confident I know how to use it correctly and that’s just one of many complicated things in C++. C++ is too subtle and I don’t want my code to be a puzzle. Possibility of optimized implementations I wrote a StrVec class that is optimized for storing vector of strings. It’s more efficient than std::vector<std::string> by a large margin and I use it extensively. Temporary allocator and pool allocators I use temporary allocators heavily. They make the code faster and smaller. Technically STL has support for non-standard allocators but the API is so bad that I would rather not. My temporary allocator and pool allocators are very small and simple and I can add support for them only when beneficial. Minimize unsigned int STL and standard C library like to use size_t and other unsigned integers. I think it was a mistake. Go shows that you can just use int. Having two types leads to cast-apalooza. I don’t like visual noise in my code. Unsigned are also more dangerous. When you substract you can end up with a bigger value. Indexing from end is subtle, for (int i = n; i >= 0; i--) is buggy because i >= 0 is always true for unsigned. Sadly I only realized this recently so there’s a lot of code still to refactor to change use of size_t to int. Mostly raw pointers No std::unique_ptr for me. Warnings are errors C++ makes a distinction between compilation errors and compilation warnings. I don’t like sloppy code and polluting build output with warning messages so for my own code I use a compiler flag that turns warnings into errors, which forces me to fix the warnings.

yesterday 2 votes
Bugs I fixed in SumatraPDF

Unexamined life is not worth living said Socrates. I don’t know about that but to become a better, faster, more productive programmer it pays to examine what makes you un-productive. Fixing bugs is one of those un-productive activities. You have to fix them but it would be even better if you didn’t write them in the first place. Therefore it’s good to reflect after fixing a bug. Why did the bug happen? Could I have done something to not write the bug in the first place? If I did write the bug, could I do something to diagnose or fix it faster? This seems like a great idea that I wasn’t doing. Until now. Here’s a random selection of bugs I found and fixed in SumatraPDF, with some reflections. SumatraPDF is a C++ win32 Windows app. It’s a small, fast, open-source, multi-format PDF/eBook/Comic Book reader. To keep the app small and fast I generally avoid using other people’s code. As a result most code is mine and most bugs are mine. Let’s reflect on those bugs. TabWidth doesn’t work A user reported that TabWidth advanced setting doesn’t work in 3.5.2 but worked in 3.4.6. I looked at the code and indeed: the setting was not used anywhere. The fix was to use it. Why did the bug happen? It was a refactoring. I heavily refactored tabs control. Somehow during the rewrite I forgot to use the advanced setting when creating the new tabs control, even though I did write the code to support it in the control. I guess you could call it sloppiness. How could I not write the bug? I could review the changes more carefully. There’s no-one else working on this project so there’s no one else to do additional code reviews. I typically do a code review by myself with webdiff but let’s face it: reviewing changes right after writing them is the worst possible time. I’m biased to think that the code I just wrote is correct and I’m often mentally exhausted. Maybe I should adopt a process when I review changes made yesterday with fresh, un-tired eyes? How could I detect the bug earlier?. 3.5.2 release happened over a year ago. Could I have found it sooner? I knew I was refactoring tabs code. I knew I have a setting for changing the look of tabs. If I connected the dots at the time, I could have tested if the setting still works. I don’t make releases too often. I could do more testing before each release and at the very least verify all advanced settings work as expected. The real problem In retrospect, I shouldn’t have implemented that feature at all. I like Sumatra’s customizability and I think it’s non-trivial contributor to it’s popularity but it took over a year for someone to notice and report that particular bug. It’s clear it’s not a frequently used feature. I implemented it because someone asked and it was easy. I should have said no to that particular request. Fix printing crash by correctly ref-counting engine Bugs can crash your program. Users rarely report crashes even though I did put effort into making it easy. When I a crash happens I have a crash handler that saves the diagnostic info to a file and I show a message box asking users to report the crash and with a press of a button I launch a notepad with diagnostic info and a browser with a page describing how to submit that as a GitHub issue. The other button is to ignore my pleas for help. Most users overwhelmingly choose to ignore. I know that because I also have crash reporting system that sends me a crash report. I get thousands of crash reports for every crash reported by the user. Therefore I’m convinced that the single most impactful thing for making software that doesn’t crash is to have a crash reporting system, look at the crashes and fix them. This is not a perfect system because all I have is a call stack of crashed thread, info about the computer and very limited logs. Nevertheless, sometimes all it takes is a look at the crash call stack and inspection of the code. I saw a crash in printing code which I fixed after some code inspection. The clue was that I was accessing a seemingly destroyed instance of Engine. That was easy to diagnose because I just refactored the code to add ref-counting to Engine so it was easy to connect the dots. I’m not a fan of ref-counting. It’s easy to mess up ref-counting (add too many refs, which leads to memory leaks or too many releases which leads to premature destruction). I’ve seen codebases where developers were crazy in love with ref-counting: every little thing, even objects with obvious lifetimes. In contrast,, that was the first ref-counted object in over 100k loc of SumatraPDF code. It was necessary in this case because I would potentially hand off the object to a printing thread so its lifetime could outlast the lifetime of the window for which it was created. How could I not write the bug? It’s another case of sloppiness but I don’t feel bad. I think the bug existed there before the refactoring and this is the hard part about programming: complex interactions between distant, in space and time, parts of the program. Again, more time spent reviewing the change could have prevented it. As a bonus, I managed to simplify the logic a bit. Writing software is an incremental process. I could feel bad about not writing the perfect code from the beginning but I choose to enjoy the process of finding and implementing improvements. Making the code and the program better over time. Tracking down a chm thumbnail crash Not all crashes can be fixed given information in crash report. I saw a report with crash related to creating a thumbnail crash. I couldn’t figure out why it crashes but I could add more logging to help figure out the issue if it happens again. If it doesn’t happen again, then I win. If it does happen again, I will have more context in the log to help me figure out the issue. Update: I did fix the crash. Fix crash when viewing favorites menu A user reported a crash. I was able to reproduce the crash and fix it. This is the bast case scenario: a bug report with instructions to reproduce a crash. If I can reproduce the crash when running debug build under the debugger, it’s typically very easy to figure out the problem and fix it. In this case I’ve recently implemented an improved version of StrVec (vector of strings) class. It had a compatibility bug compared to previous implementation in that StrVec::InsertAt(0) into an empty vector would crash. Arguably it’s not a correct usage but existing code used it so I’ve added support to InsertAt() at the end of vector. How could I not write the bug? I should have written a unit test (which I did in the fix). I don’t blindly advocate unit tests. Writing tests has a productivity cost but for such low-level, relatively tricky code, unit tests are good. I don’t feel too bad about it. I did write lots of tests for StrVec and arguably this particular usage of InsertAt() was borderline correct so it didn’t occur to me to test that condition. Use after free I saw a crash in crash reports, close to DeleteThumbnailForFile(). I looked at the code: if (!fs->favorites->IsEmpty()) { // only hide documents with favorites gFileHistory.MarkFileInexistent(fs->filePath, true); } else { gFileHistory.Remove(fs); DeleteDisplayState(fs); } DeleteThumbnailForFile(fs->filePath); I immediately spotted suspicious part: we call DeleteDisplayState(fs) and then might use fs->filePath. I looked at DeleteDisplayState and it does, in fact, deletes fs and all its data, including filePath. So we use freed data in a classic use after free bug. The fix was simple: make a copy of fs->filePath before calling DeleteDisplayState and use that. How could I not write the bug? Same story: be more careful when reviewing the changes, test the changes more. If I fail that, crash reporting saves my ass. The bug didn’t last more than a few days and affected only one user. I immediately fixed it and published an update. Summary of being more productive and writing bug free software If many people use your software, a crash reporting system is a must. Crashes happen and few of them are reported by users. Code reviews can catch bugs but they are also costly and reviewing your own code right after you write it is not a good time. You’re tired and biased to think your code is correct. Maybe reviewing the code a day after, with fresh eyes, would be better. I don’t know, I haven’t tried it.

2 days ago 3 votes
Implementation of optimized vector of strings in C++ in SumatraPDF

SumatraPDF is a fast, small, open-source PDF reader for Windows, written in C++. This article describes how I implemented StrVec class for efficiently storing multiple strings. Much ado about the strings Strings are among the most used types in most programs. Arrays of strings are also used often. I count ~80 uses of StrVec in SumatraPDF code. This article describes how I implemented an optimized array of strings in SumatraPDF C++ code . No STL for you Why not use std::vector<std::string>? In SumatraPDF I don’t use STL. I don’t use std::string, I don’t use std::vector. For me it’s a symbol of my individuality, and my belief in personal freedom. As described here, minimum size of std::string on 64-bit machines is 32 bytes for msvc / gcc and 24 bytes for short strings (15 chars for msvc / gcc, 22 chars for clang). For longer strings we have more overhead: 32⁄24 bytes for the header memory allocator overhead allocator metadata padding due to rounding allocations to at least 16 bytes There’s also std::vector overhead: for fast appends (push()) std::vectorimplementations over-allocated space Longer strings are allocated at random addresses so they can be spread out in memory. That is bad for cache locality and that often cause more slowness than executing lots of instructions. Design and implementation of StrVec StrVec (vector of strings) solves all of the above: per-string overhead of only 8 bytes strings are laid out next to each other in memory StrVec High level design of StrVec: backing memory is allocated in singly-linked pages similar to std::vector, we start with small page and increase the size of the page. This strikes a balance between speed of accessing a string at random index and wasted space unlike std::vector we don’t reallocate memory (most of the time). That saves memory copy when re-allocating backing space Here’s all there is to StrVec: struct StrVec { StrVecPage* first = nullptr; int nextPageSize = 256; int size = 0; } size is a cached number of strings. It could be calculated by summing the size in all StrVecPages. nextPageSize is the size of the next StrVecPage. Most array implementation increase the size of next allocation by 1.4x - 2x. I went with the following progression: 256 bytes, 1k, 4k, 16k, 32k and I cap it at 64k. I don’t have data behind those numbers, they feel right. Bigger page wastes more space. Smaller page makes random access slower because to find N-th string we need to traverse linked list of StrVecPage. nextPageSize is exposed to allow the caller to optimize use. E.g. if it expects lots of strings, it could set nextPageSize to a large number. StrVecPage Most of the implementation is in StrVecPage. The big idea here is: we allocate a block of memory strings are allocated from the end of memory block at the beginning of the memory block we build and index of strings. For each string we have: u32 size u32 offset of the string within memory block, counting from the beginning of the block The layout of memory block is: StrVecPage struct { size u32; offset u32 } [] … not yet used space strings This is StrVecPage: struct StrVecPage { struct StrVecPage* next; int pageSize; int nStrings; char* currEnd; } next is for linked list of pages. Since pages can have various sizes we need to record pageSize. nStrings is number of strings in the page and currEnd points to the end of free space within page. Implementing operations Appending a string Appending a string at the end is most common operation. To append a string: we calculate how much memory inside a page it’ll need: str::Len(string) + 1 + sizeof(u32) + sizeof(u32). +1 is for 0-termination for compatibility with C APIs that take char*, and 2xu32 for size and offset. If we have enough space in last page, we add size and offset at the end of index and append a string from the end i.e. `currEnd - (str::Len(string) + 1). If there is not enough space in last page, we allocate new page We can calculate how much space we have left with: int indexEntrySize = sizeof(u32) + sizeof(u32); // size + offset char* indexEnd = (char*)pageStart + sizeof(StrVecPage) + nStrings*indexEntrySize int nBytesFree = (int)(currEnd - indexEnd) Removing a string Removing a string is easy because it doesn’t require moving memory inside StrVecPage. We do nStrings-- and move index values of strings after the removed string. I don’t bother freeing the string memory within a page. It’s possible but complicated enough I decided to skip it. You can compact StrVec to remove all overhead. If you do not care about preserving order of strings after removal, I haveRemoveAtFast() which uses a trick: instead of copying memory of all index values after removed string, I copy a single index from the end into a slot of the string being removed. Replacing a string or inserting in the middle Replacing a string or inserting a string in the middle is more complicated because there might not be enough space in the page for the string. When there is enough space, it’s as simple as append. When there is not enough space, I re-use the compacting capability: I compact all existing pages into a single page with extra space for the string and some extra space as an optimization for multiple inserts. Iteration A random access requires traversing a linked list. I think it’s still fast because typically there aren’t many pages and we only need to look at a single nStrings value. After compaction to a single page, random access is as fast as it could ever be. C++ iterator is optimized for sequential access: struct iterator { const StrVec* v; int idx; // perf: cache page, idxInPage from prev iteration int idxInPage; StrVecPage* page; } We cache the current state of iteration as page and idxInPage. To advance to next string we advance idxInPage. If it exceeds nStrings, we advance to page->next. Optimized search Finding a string is as optimized as it could be without a hash table. Typically to compare char* strings you need to call str::Eq(s, s2) for every string you compare it to. That is a function call and it has to touch s2 memory. That is bad for performance because it blows the cache. In StrVec I calculate length of the string to find once and then traverse the size / offset index. Only when size is different I have to compare the strings. Most of the time we just look at offset / size in L1 cache, which is very fast. Compacting If you know that you’ll not be adding more strings to StrVec you can compact all pages into a single page with no overhead of empty space. It also speeds up random access because we don’t have multiple pages to traverse to find the item and a given index. Representing a nullptr char* Even though I have a string class, I mostly use char* in SumatraPDF code. In that world empty string and nullptr are 2 different things. To allow storing nullptr strings in StrVec (and not turning them into empty strings on the way out) I use a trick: a special u32 value kNullOffset represents nullptr. StrVec is a string pool allocator In C++ you have to track the lifetime of each object: you allocate with malloc() or new when you no longer need to object, you call free() or delete However, the lifetime of allocations is often tied together. For example in SumatraPDF an opened document is represented by a class. Many allocations done to construct that object last exactly as long as the object. The idea of a pool allocator is that instead of tracking the lifetime of each allocation, you have a single allocator. You allocate objects with the same lifetime from that allocator and you free them with a single call. StrVec is a string pool allocator: all strings stored in StrVec have the same lifetime. Testing In general I don’t advocate writing a lot of tests. However, low-level, tricky functionality like StrVec deserves decent test coverage to ensure basic functionality works and to exercise code for corner cases. I have 360 lines of tests for ~700 lines of of implementation. Potential tweaks and optimization When designing and implementing data structures, tradeoffs are aplenty. Interleaving index and strings I’m not sure if it would be faster but instead of storing size and offset at the beginning of the page and strings at the end, we could store size / string sequentially from the beginning. It would remove the need for u32 of offset but would make random access slower. Varint encoding of size and offset Most strings are short, under 127 chars. Most offsets are under 16k. If we stored size and offset as variable length integers, we would probably bring down average per-string overhead from 8 bytes to ~4 bytes. Implicit size When strings are stored sequentially size is implicit as difference between offset of the string and offset of next string. Not storing size would make insert and set operations more complicated and costly: we would have to compact and arrange strings in order every time. Storing index separately We could store index of size / offset in a separate vector and use pages to only allocate string data. This would simplify insert and set operations. With current design if we run out of space inside a page, we have to re-arrange memory. When offset is stored outside of the page, it can refer to any page so insert and set could be as simple as append. The evolution of StrVec The design described here is a second implementation of StrVec. The one before was simply a combination of str::Str (my std::string) for allocating all strings and Vec<u32> (my std::vector) for storing offset index. It had some flaws: appending a string could re-allocate memory within str::Str. The caller couldn’t store returned char* pointer because it could be invalidated. As a result the API was akward and potentially confusing: I was returning offset of the string so the string was str::Str.Data() + offset. The new StrVec doesn’t re-allocate on Append, only (potentially) on InsertAt and SetAt. The most common case is append-only which allows the caller to store the returned char* pointers. Before implementing StrVec I used Vec<char*>. Vec is my version of std::vector and Vec<char*> would just store pointer to individually allocated strings. Cost vs. benefit I’m a pragmatist: I want to achieve the most with the least amount of code, the least amount of time and effort. While it might seem that I’m re-implementing things willy-nilly, I’m actually very mindful of the cost of writing code. Writing software is a balance between effort and resulting quality. One of the biggest reasons SumatraPDF so popular is that it’s fast and small. That’s an important aspect of software quality. When you double click on a PDF file in an explorer, SumatraPDF starts instantly. You can’t say that about many similar programs and about other software in general. Keeping SumatraPDF small and fast is an ongoing focus and it does take effort. StrVec.cpp is only 705 lines of code. It took me several days to complete. Maybe 2 days to write the code and then some time here and there to fix the bugs. That being said, I didn’t start with this StrVec. For many years I used obvious Vec<char*>. Then I implemented somewhat optimized StrVec. And a few years after that I implemented this ultra-optimized version. References SumatraPDF is a small, fast, multi-format (PDF/eBook/Comic Book and more), open-source reader for Windows. The implementation described here: StrVec.cpp, StrVec.h, StrVec_ut.cpp By the time you read this, the implementation could have been improved.

3 days ago 4 votes
Custom search UI in CodeMirror 6 and Svelte 5

CodeMirror 6 has @codemirror/search package which provides UI for searching within a document, triggered via Ctrl + F. In my note-taking application Edna I wanted something slightly different. This article describes how I implemented it. The UI went from: to: CodeMirror is very customizable which is great, but makes it hard to understand how to put the pieces together to achieve desired results. Almost all of the work is done in @codemirror/search, I just plugged my own UI into framework designed by the author of CodeMirror. How to get standard search UI in CodeMirror When you create CodeMirror you configure it with: import { highlightSelectionMatches, searchKeymap, } from "@codemirror/search"; EditorState.create({ // ... other stuff extensions: [ // ... other stuff highlightSelectionMatches(), keymap.of([ // ... other stuff ...searchKeymap, ]), ] }) searchKeymap is what registers key bindings like Ctrl + F to invoke search UI, F3 to find next match etc. highlightSelectionMatches is an extension that visually highlights search matches. Customizing the UI CodeMirror 6 has a notion of UI panels. Built-in search UI is a panel. Custom search UI panel Thankfully panel is as generic as it can be: it’s just a div hosting the UI. The author predicted the need for providing custom search UI so it’s as easy as adding search extension configured with custom search panel creation function: import { search, } from "@codemirror/search"; function createFindPanel() { ... } EditorState.create({ // ... other stuff extensions: [ // ... other stuff search({ createPanel: createFnddPanel, }), ] }) All the options to search() are documented here. Create the panel Function that creates the panel returns a DOM element e.g. a <div>. You can create that element using vanilla JavaScript or using a framework like Svelte, React, Vue. For Svelte the trick is to manually instantiate the component. I use Svelte 5 so I’ve created Find.svelte component which floats over the editor area thanks to position: fixed. Here’s how to manually mount it: import Find from "../components/Find.svelte"; import { mount } from "svelte"; function createFnddPanel(view) { const dom = document.createElement("div"); const args = { target: dom, props: { view, }, }; mount(Find, args); return { dom, top: true, }; } If you provide createPanel function, @codemirror/search will call it to create search UI instead of its own. It’s a great design because it reuses most of the code in @codemirror/search. The UI can be triggered programmatically, by calling openSearchPanel(EditorView) (and closed with closeSearchPanel(EditorView). Or By Mod + F key binding defined in searchKeymap. You can change the binding by not including searchKeymap and instead provide your own array of bindings to functions from @codemirror/search. By default CodeMirror shrinks the editor area to host the UI. It can host it either at the top or the bottom of the editor, which is what top return value indicates. In my case value of top doesn’t matter because my UI floats on top of editor with position: fixed and z-index: 20 so we don’t shrink the editor area. The DOM element you create is hosted within this structure: <div class="cm-panels cm-panels-top" style="top: 0px;"> <div class="cm-panel"> <!-- YOUR DOM ELEMENT --> </div> </div> My CSS provided with EditorView.theme() was: const themeBase = EditorView.theme({ ".cm-panels .cm-panel": { boxShadow: "0 0 10px rgba(0,0,0,0.15)", padding: "8px 12px", }, }); The padding made the wrapper element visible even though I didn’t want it. To fix it I simply changed it to: EditorView.theme({ ".cm-panels .cm-panel": { }, }); Doing the searches When user changes the text in input field, we need tell CodeMirror 6 to do the search. You talk to CodeMirror using those commands. To start a new search you do: let query = new SearchQuery({ search: searchTerm, replace: replaceTerm, // if you're going to run replacement commands caseSensitive: false, literal: true, }); view.dispatch({ effects: setSearchQuery.of(query), }); CodeMirror 6 supports regex search, matching case, matching only whole world option. See SearchQuery docs. To instruct CodeMirror to navigate to next, previous match etc. you call: findNext : advance to next match in the editor findPrevious : go to previous match replaceNext : replace next match replaceAll : replace all matches All those function take EditorView as an argument and act based on the last SearchQuery. All commands are documented here. Doing it in Svelte 5 Here’s the core of the component: <div class="flex"> <input bind:this={searchInput} type="text" spellcheck="false" placeholder="Find" bind:value={searchTerm} class="w-[32ch]" use:focus onkeydown={onKeyDown} /> <button onclick={next} title="find next (Enter}">next</button> <button onclick={prev} title="find previous (Shift + Enter)">prev </button> <button onclick={all} title="find all">all </button> </div> <div class="flex"> <input type="text" spellcheck="false" placeholder="Replace" bind:value={replaceTerm} class="w-[32ch]" /> <button onclick={replace}>replace</button> <button onclick={_replaceAll} class="grow">all</button> </div> We do “search as you type” by observing changes to searchTerm input field: $effect(() => { let query = new SearchQuery({ search: searchTerm, replace: replaceTerm, caseSensitive: false, literal: true, }); view.dispatch({ effects: setSearchQuery.of(query), }); }); On button press we invoke desired functionality, like: function next() { findNext(view); } Pre-populating input from selection When we show search UI it’s nice to pre-populate search term with current selection. It’s as easy as: import { getSearchQuery, } from "@codemirror/search"; let query = getSearchQuery(view.state); searchTerm = query.search; This must be done on component initialization, not in onMount(). As addition trick, we select the content of input field: onMount(() => { tick().then(() => { searchInput.select(); }); }); Closing search panel on Esc I wanted to hide search UI when Escape key is pressed. Thankfully we get searchPanelOpen(EditorView) function that tells us if search panel is open and closeSearchPanel(EditorView) to close. So it’s as easy as: function onKeyDown(ev) { if (ev.key === "Escape") { let view = getEditorView(); if (view && searchPanelOpen(view.state)) { closeSearchPanel(view); return; } } } Customizing the look of search matches CodeMirror 6 is built on web technologies so the way it allows customizing the look of things is by applying known CSS styles. You provide your own CSS to change the look of things. Here’s the CSS for search matches: <!-- this is how all matches are highlighted --> <span class="cm-searchMatch"><span class="cm-selectionMatch">another</span></span> <!-- this is how currently selected match is higlighted. It changes with findNext() / findPrevious() / selectMatches() --> <span class="cm-searchMatch cm-searchMatch-selected">another</span> How to figure things out When I started working on this I did not know any of the above. Here’s my strategy for figuring this out. Look at the source code We live in open source world. The code to @codemirror/search is available so the first step was to look at it to see exported APIs etc. Look at the docs Ok, not really. I knew so little that even though CodeMirror has extensive documentation, I just couldn’t figure out how to put the pieces together. Ask omniscient AI I saw that there is setSearchQuery API but I didn’t know how to use it. I asked Grok: how to use setSearchQuery from @codemirror/search package in codemirror 6 It gave me a good response. Look at the code again So I tried sending new SearchQuery to the editor and it didn’t work i.e. I didn’t see the matches highlighted. Back to reading the code and I see that in searchHighlighter higlight() function, it doesn’t do anything if there’s no panel. But I want my own UI, not their panel, so hmm… See how others did it Surely there must be some open source project that did something similar. The trick is to find it. I used GitHub code search to look for distinct APIs, which is harder than it looks. If you search for findNext you’ll be flooded with results. So I searched for uses of @codemirror/search. I found a few projects that created custom search UIs and that gave me enough hints on how to use the APIs and how to put all the available pieces together. Resources Edna is a note taking application for developers and power users documentation of @codemirror/search my full implementation is in Find.svelte another implementation in Vue another implementation in vanilla JavaScript

4 days ago 4 votes

More in programming

Logical Quantifiers in Software

I realize that for all I've talked about Logic for Programmers in this newsletter, I never once explained basic logical quantifiers. They're both simple and incredibly useful, so let's do that this week! Sets and quantifiers A set is a collection of unordered, unique elements. {1, 2, 3, …} is a set, as are "every programming language", "every programming language's Wikipedia page", and "every function ever defined in any programming language's standard library". You can put whatever you want in a set, with some very specific limitations to avoid certain paradoxes.2 Once we have a set, we can ask "is something true for all elements of the set" and "is something true for at least one element of the set?" IE, is it true that every programming language has a set collection type in the core language? We would write it like this: # all of them all l in ProgrammingLanguages: HasSetType(l) # at least one some l in ProgrammingLanguages: HasSetType(l) This is the notation I use in the book because it's easy to read, type, and search for. Mathematicians historically had a few different formats; the one I grew up with was ∀x ∈ set: P(x) to mean all x in set, and ∃ to mean some. I use these when writing for just myself, but find them confusing to programmers when communicating. "All" and "some" are respectively referred to as "universal" and "existential" quantifiers. Some cool properties We can simplify expressions with quantifiers, in the same way that we can simplify !(x && y) to !x || !y. First of all, quantifiers are commutative with themselves. some x: some y: P(x,y) is the same as some y: some x: P(x, y). For this reason we can write some x, y: P(x,y) as shorthand. We can even do this when quantifying over different sets, writing some x, x' in X, y in Y instead of some x, x' in X: some y in Y. We can not do this with "alternating quantifiers": all p in Person: some m in Person: Mother(m, p) says that every person has a mother. some m in Person: all p in Person: Mother(m, p) says that someone is every person's mother. Second, existentials distribute over || while universals distribute over &&. "There is some url which returns a 403 or 404" is the same as "there is some url which returns a 403 or some url that returns a 404", and "all PRs pass the linter and the test suites" is the same as "all PRs pass the linter and all PRs pass the test suites". Finally, some and all are duals: some x: P(x) == !(all x: !P(x)), and vice-versa. Intuitively: if some file is malicious, it's not true that all files are benign. All these rules together mean we can manipulate quantifiers almost as easily as we can manipulate regular booleans, putting them in whatever form is easiest to use in programming. Speaking of which, how do we use this in in programming? How we use this in programming First of all, people clearly have a need for directly using quantifiers in code. If we have something of the form: for x in list: if P(x): return true return false That's just some x in list: P(x). And this is a prevalent pattern, as you can see by using GitHub code search. It finds over 500k examples of this pattern in Python alone! That can be simplified via using the language's built-in quantifiers: the Python would be any(P(x) for x in list). (Note this is not quantifying over sets but iterables. But the idea translates cleanly enough.) More generally, quantifiers are a key way we express higher-level properties of software. What does it mean for a list to be sorted in ascending order? That all i, j in 0..<len(l): if i < j then l[i] <= l[j]. When should a ratchet test fail? When some f in functions - exceptions: Uses(f, bad_function). Should the image classifier work upside down? all i in images: classify(i) == classify(rotate(i, 180)). These are the properties we verify with tests and types and MISU and whatnot;1 it helps to be able to make them explicit! One cool use case that'll be in the book's next version: database invariants are universal statements over the set of all records, like all a in accounts: a.balance > 0. That's enforceable with a CHECK constraint. But what about something like all i, i' in intervals: NoOverlap(i, i')? That isn't covered by CHECK, since it spans two rows. Quantifier duality to the rescue! The invariant is equivalent to !(some i, i' in intervals: Overlap(i, i')), so is preserved if the query SELECT COUNT(*) FROM intervals CROSS JOIN intervals … returns 0 rows. This means we can test it via a database trigger.3 There are a lot more use cases for quantifiers, but this is enough to introduce the ideas! Next week's the one year anniversary of the book entering early access, so I'll be writing a bit about that experience and how the book changed. It's crazy how crude v0.1 was compared to the current version. MISU ("make illegal states unrepresentable") means using data representations that rule out invalid values. For example, if you have a location -> Optional(item) lookup and want to make sure that each item is in exactly one location, consider instead changing the map to item -> location. This is a means of implementing the property all i in item, l, l' in location: if ItemIn(i, l) && l != l' then !ItemIn(i, l'). ↩ Specifically, a set can't be an element of itself, which rules out constructing things like "the set of all sets" or "the set of sets that don't contain themselves". ↩ Though note that when you're inserting or updating an interval, you already have that row's fields in the trigger's NEW keyword. So you can just query !(some i in intervals: Overlap(new, i')), which is more efficient. ↩

23 hours ago 3 votes
Setting Element Ordering With HTML Rewriter Using CSS

After shipping my work transforming HTML with Netlify’s edge functions I realized I have a little bug: the order of the icons specified in the URL doesn’t match the order in which they are displayed on screen. Why’s this happening? I have a bunch of links in my HTML document, like this: <icon-list> <a href="/1/">…</a> <a href="/2/">…</a> <a href="/3/">…</a> <!-- 2000+ more --> </icon-list> I use html-rewriter in my edge function to strip out the HTML for icons not specified in the URL. So for a request to: /lookup?id=1&id=2 My HTML will be transformed like so: <icon-list> <!-- Parser keeps these two --> <a href="/1/">…</a> <a href="/2/">…</a> <!-- But removes this one --> <a href="/3/">…</a> </icon-list> Resulting in less HTML over the wire to the client. But what about the order of the IDs in the URL? What if the request is to: /lookup?id=2&id=1 Instead of: /lookup?id=1&id=2 In the source HTML document containing all the icons, they’re marked up in reverse chronological order. But the request for this page may specify a different order for icons in the URL. So how do I rewrite the HTML to match the URL’s ordering? The problem is that html-rewriter doesn’t give me a fully-parsed DOM to work with. I can’t do things like “move this node to the top” or “move this node to position x”. With html-rewriter, you only “see” each element as it streams past. Once it passes by, your chance at modifying it is gone. (It seems that’s just the way these edge function tools are designed to work, keeps them lean and performant and I can’t shoot myself in the foot). So how do I change the icon’s display order to match what’s in the URL if I can’t modify the order of the elements in the HTML? CSS to the rescue! Because my markup is just a bunch of <a> tags inside a custom element and I’m using CSS grid for layout, I can use the order property in CSS! All the IDs are in the URL, and their position as parameters has meaning, so I assign their ordering to each element as it passes by html-rewriter. Here’s some pseudo code: // Get all the IDs in the URL const ids = url.searchParams.getAll("id"); // Select all the icons in the HTML rewriter.on("icon-list a", { element: (element) => { // Get the ID const id = element.getAttribute('id'); // If it's in our list, set it's order // position from the URL if (ids.includes(id)) { const order = ids.indexOf(id); element.setAttribute( "style", `order: ${order}` ); // Otherwise, remove it } else { element.remove(); } }, }); Boom! I didn’t have to change the order in the source HTML document, but I can still get the displaying ordering to match what’s in the URL. I love shifty little workarounds like this! Email · Mastodon · Bluesky

23 hours ago 2 votes
The missing part of Espressif’s reset circuit

In the previous article, we peeked at the reset circuit of ESP-Prog with an oscilloscope, and reproduced it with basic components. We observed that it did not behave quite as expected. In this article, we’ll look into the missing pieces. An incomplete circuit For a hint, we’ll first look a bit more closely at the … Continue reading The missing part of Espressif’s reset circuit → The post The missing part of Espressif’s reset circuit appeared first on Quentin Santos.

23 hours ago 2 votes
All about Svelte 5 snippets

Snippets are a useful addition to Svelte 5. I use them in my Svelte 5 projects like Edna. Snippet basics A snippet is a function that renders html based on its arguments. Here’s how to define and use a snippet: {#snippet hello(name)} <div>Hello {name}!</div> {/snippet} {@render hello("Andrew")} {@render hello("Amy")} You can re-use snippets by exporting them: <script module> export { hello }; </script> {@snippet hello(name)}<div>Hello {name}!</div>{/snippet} Snippets use cases Snippets for less nesting Deeply nested html is hard to read. You can use snippets to extract some parts to make the structure clearer. For example, you can transform: <div> <div class="flex justify-end mt-2"> <button onclick={onclose} class="mr-4 px-4 py-1 border border-black hover:bg-gray-100" >Cancel</button > <button onclick={() => emitRename()} disabled={!canRename} class="px-4 py-1 border border-black hover:bg-gray-50 disabled:text-gray-400 disabled:border-gray-400 disabled:bg-white default:bg-slate-700" >Rename</button > </div> into: {#snippet buttonCancel()} <button onclick={onclose} class="mr-4 px-4 py-1 border border-black hover:bg-gray-100" >Cancel</button > {/snippet} {#snippet buttonRename()}...{/snippet} To make this easier to read: <div> <div class="flex justify-end mt-2"> {@render buttonCancel()} {@render buttonRename()} </div> </div> snippets replace default <slot/> In Svelte 4, if you wanted place some HTML inside the component, you used <slot />. Let’s say you have Overlay.svelte component used like this: <Overlay> <MyDialog></MyDialog> </Overlay> In Svelte 4, you would use <slot /> to render children: <div class="overlay-wrapper"> <slot /> </div> <slot /> would be replaced with <MyDialog></MyDialog>. In Svelte 5 <MyDialog></MyDialog> is passed to Overlay.svelte as children property so you would change Overlay.svelte to: <script> let { children } = $props(); </script> <div class="overlay-wrapper"> {@render children()} </div> children property is created by Svelte compiler so you should avoid naming your own props children. snippets replace named slots A component can have a default slot for rendering children and additional named slots. In Svelte 5 instead of named slots you pass snippets as props. An example of Dialog.svelte: <script> let { title, children } = $props(); </script> <div class="dialog"> <div class="title"> {@render title()} </div> {@render children()} </div> And use: {#snippet title()} <div class="fancy-title">My fancy title</div> {/snippet} <Dialog title={title}> <div>Body of the dialog</div> </Dialog> passing snippets as implicit props You can pass title snippet prop implicitly: <Dialog> {#snippet title()} <div class="fancy-title">My fancy title</div> {/snippet} <div>Body of the dialog</div> </Dialog> Because {snippet title()} is a child or <Dialog>, we don’t have to pass it as explicit title={title} prop. The compiler does it for us. snippets to reduce repetition Here’s part of how I render https://tools.arslexis.io/ {#snippet row(name, url, desc)} <tr> <td class="text-left align-top" ><a class="font-semibold whitespace-nowrap" href={url}>{name}</a> </td> <td class="pl-4 align-top">{@html desc}</td> </tr> {/snippet} {@render row("unzip", "/unzip/", "unzip a file in the browser")} {@render row("wc", "/wc/", "like <tt>wc</tt>, but in the browser")} It saves me copy & paste of the same HTML and makes the structure more readable. snippets for recursive rendering Sometimes you need to render a recursive structure, like nested menus or file tree. In Svelte 4 you could use <svelte:self> but the downside of that is that you create multiple instances of the component. That means that the state is also split among multiple instances. That makes it harder to implement functionality that requires a global view of the structure, like keyboard navigation. With snippets you can render things recursively in a single instance of the component. I used it to implement nested context menus. snippets to customize rendering Let’s say you’re building a Menu component. Each menu item is a <div> with some non-trivial children. To allow the client of Menu customize how items are rendered, you could provide props for things like colors, padding etc. or you could allow ultimate flexibility by accepting an optional menuitem prop that is a snippet that renders the item. You can think of it as a headless UI i.e. you provide the necessary structure and difficult logic like keyboard navigation etc. and allow the client lots of control over how things are rendered. snippets for library of icons Before snippets every SVG Icon I used was a Svelte component. Many icons means many files. Now I have a single Icons.svelte file, like: <script module> export { IconMenu, IconSettings }; </script> {#snippet IconMenu(arg1, arg2, ...)} <svg>... icon svg</svg> {/snippet}} {#snippet IconSettings()} <svg>... icon svg</svg> {/snippet}}

18 hours ago 2 votes
Another tip (tip)
2 hours ago 1 votes