4 ms·
I wrote a string type
- brundolf 3y agoI've never seen an article with a minimap on the side before, that's kinda awesome
- chrismorgan 3y agoI’m genuinely disappointed that it’s not done with -moz-element() on Firefox, but still duplicates all the content and just scales it down. Using -moz-element() has the potentially-useful side-effect that things like text selection will be visible in the minimap as well, as well as avoiding the problems of the duplication approach, such as that browser find functionality looks in the minimap too. (The minimap needs `user-select: none` which fixes some of the problems, but not all.) I still hope that other browsers will eventually implement element(), along with cross-fade() which is also in the CSS Images Module Level 4 draft <https://w3c.github.io/csswg-drafts/css-images-4/ https://w3c.github.io/csswg-drafts/css-images-4/>.
- kelnos 3y ago> I’m genuinely disappointed that it’s not done with -moz-element() on Firefox Given how few of us Firefox users there are out there, I'm sadly not surprised.
- msm_ 3y agoIn this case you might be interested in this recent post: https://news.ycombinator.com/item?id=36757542 https://news.ycombinator.com/item?id=36757542.
- Propelloni 3y agoAgreed, it's a joy to scroll through this article using the minimap. IMO a stark reminder how useless modern scrollbars have become.
- NooneAtAll3 3y agoit doesn't even appear for me on default browser scaling if you hadn't commented that, I wouldn't have known
- karmakaze 3y agoAnother useful datatype is a rope[0]. It is useful for using immutable/shared pieces that can build up to other longer compositions. In particular, an operation such as concatenation can be O(1) since that's matches the representation of a rope. [0] https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure)
- jcparkyn 3y agoAlso worth noting that just about every javascript engine uses ropes internally to represent strings (most of the time). https://docs.google.com/document/d/1o-MJPAddpfBfDZCkIHNKbMiM86iDFld7idGbNQLuKIQ/preview#heading=h.6kknmf22ixwc https://docs.google.com/document/d/1o-MJPAddpfBfDZCkIHNKbMiM...
- codethief 3y ago> most of the time Looking at the reference[0] given at the very end of the document, wouldn't the word "sometimes" be more appropriate? [0]: https://mrale.ph/blog/2016/11/23/making-less-dart-faster.html https://mrale.ph/blog/2016/11/23/making-less-dart-faster.htm...
- jcparkyn 3y agoInteresting, seems like things are more complicated than I thought.
- shirleyquirk 3y agoThe Nim compiler used ropes internally for years, until recently[0] because removing them reduced memory consumption and decreased compile times, so ymmv [0]https://github.com/nim-lang/Nim/pull/20433 https://github.com/nim-lang/Nim/pull/20433
- dietr1ch 3y agoThis is a big tell that maybe we don't want to know exactly the type, but to have way to let the compiler/benchmarks to pick the best performing data structure for the task at hand, but I think that on most programming languages neither the language nor the tooling help you too much here.* *Saying this mostly with the intent of being proved wrong ;) kxcd://386
- Joker_vD 3y agoOr you can replace the escape sequences right in the source text: it works since no escape sequence is shorter than the text it represents.
- ksaj 3y agoWhat about \n, which decodes to 0x0ah - two bytes to one byte? I can't think of any others like that, but newline in different OS's get represented in various different ways (like DOS's famous CRLF, which adds an 0x0dh to the recipe). Operating systems that use 0x0ah alone could very well be the only example.
- dietr1ch 3y agoNote that while in your compiler you don't really care about the representation that the OS expect in real files. It's ok for your intermediate, in-memory representation to be meaningless to the OS. Also, maybe it's not a literal character for character replacement. Since lengths are probably changing, your pre-processed input might be shorter (or longer if you truly need to expand some escaped chars (and you have a program that just wants to break your compiler by abusing that escape sequence :P))
- ksaj 3y agoYes, but some OS's use 0x0ah alone, which is half the bytes of \n representation. People from the 90's will easily remember navigating the ^M (which is the 0x0dh showing up) showing up at the end of every line in a DOS text file when viewing them under a Linux text editor.
- dietr1ch 3y agoThis is a different problem around how to interpret new lines from a Windows file (\r\n) or maybe an old Mac version (\n\r to keep things incompatible I guess). If you are not happy with the OS's choice for new lines, you can pre-process that when reading the input as the very first stage. This is what I meant when I said that your compiler doesn't really care about the OS's semantics once the file is in memory, you only need to respect them if you are writing intermediate state to files (like some IR). The article is talking about how to handle escaped characters in the source, like literal `\n` you can see on `let hi = "Hello\nWorld\nfrom my compiler!"` using your average text editor (0x5c+0x6e in ASCII), and how to build an efficient string type that mostly borrows views from the in-memory version of the source file (which could be a pre-processed version of the raw file if you hate odd line breaks).
- emodendroket 3y agoJust goes to show how much work goes into the illusion that strings are a simple data type.
- tonyedgecombe 3y agoEverything is more complex than it first seems in this industry.
- danjc 3y agoEverything is more complex than it seems.
- ithkuil 3y agoAnd even things which are now relatively simple and the same in every language and hardware platform become complex if you look through the lens of history and see the various alternatives that have been explored. E.g. signed integers
- fjfaase 3y agoNice library with many features. But I do not always understand the focus on memory usage. I guess that the reason behind this is that less memory allocations, have a positive effect on execution times. In a parser, where you often have to compare identifiers, it is a good idea to put all strings for identifiers into a unique pointer with the help of a hash table. In my interpreting parser [1] I use a hexa hash tree [2] for storing identifiers. It is not very memory efficient, but very fast. It turns every string (from the input buffer) into a unique pointer for that string pointing to a copy of the string. In this way comparing string (identifiers) is equivalent to comparing pointers. The idea of the hexa hash tree is that is a tree where each node has sixteen child nodes. Which node is selected is based on a step wise evaluated hash function that first takes the lower four bytes of successive characters in the string, and after reaching the end of the string, the higher four bytes of the characters. The nodes often taken up more memory space than the strings themselves. [1] https://github.com/FransFaase/IParse/ https://github.com/FransFaase/IParse/ [2] https://github.com/FransFaase/IParse/blob/master/software/Ident.cpp https://github.com/FransFaase/IParse/blob/master/software/Id...
- Sharlin 3y agoNot just allocations, but critically – especially on modern machines – cache coherency. Indirections are an enemy of performance, and indirections to many different parts of memory in particular. A custom allocator can be a great help though, especially in a compiler where you can pretty much just use a fast slab/bump allocator and not worry about freeing memory until the end.
- TazeTSchnitzel 3y agoDo you mean cache locality? Coherence is not something ordinary single-threaded code has to be concerned with.
- Sharlin 3y agoOops, indeed, brain fart.
- 3y ago
- sparkie 3y agoOn footnote #4. The change from two shifts to movabs/and is only possible for unsigned. If the size was signed this wouldn't be the correct behavior (Requires sar instead of shr). It's not surprising that RISC-V sticks to using two shifts because it takes a bunch of instructions to load a 64-bit constant into a register. Can't even load a 32-bit constant into register with a single instruction on RV.
- snvzz 3y ago>Can't even load a 32-bit constant into register with a single instruction on RV. Just do it in the standard way, and not concern yourself with hardware implementation details. RISC-V assembly language even has standardized pseudoinstructions to do just that. Some implementations will see the multiple opcodes as one instructions. Others won't. It's not for the programmer to worry about.
- sparkie 3y agoThe standard does not actually specify what sequence of instructions to use for the load pseudo-instruction, so it is left up to the assembler to decide. A 32-bit load still requires 2 instructions (The purpose of the lui instruction is to make this efficient). A 64-bit load requires loading 2 32-bit values, shifting one 32-bits right then performing a bitwise or. Alternatively you can hold the 64-bit value in .rodata and use a single instruction to load it. The point is, it takes several more instruction bits and/or cycles than a `shr 2; sar 2` for clearing the two MSBs, so the optimisation given for x86 for this sequence is not useful here and the trivial solution is better. A solution that may be better elsewhere is `btr 63; btr 62`. Since RV can specify a different destination operand you don't need an extra mov instruction as the x86 version would require.
- auggierose 3y agoI feel most code in Rust falls into the premature optimisation bucket. To prototype/hack something, TypeScript is a much better choice. To then carefully optimise something, Rust is not high-level enough for me, and too restrictive in what you can do. The kind of high-level environment I am looking for here does not exist yet, so I guess people go for Rust because there is no better choice, but it feels like a dead end to me.
- TwentyPosts 3y agoHow 'high-level' are you hoping for here? Haskell? Rust has very high abstractions, but I guess the fundamentals are based around giving you control over low level stuff, which seems like a good balance to me. I'm not sure what specifically you'd hope to do which you can't do in Rust.
- auggierose 3y agoThere is a lot of stuff you cannot do in Rust. For example reasoning about your code, which is the minimum I expect from my language. If you cannot do that, it's not high-level enough. Rust is like all other type-based languages: it restricts what you can do, offering you some guarantees in return. For me, the deal Rust is offering is just not that good. I don't like to live in somebody else's idea of allowed code.
- TwentyPosts 3y agoYou can't..."reason about your code" in Rust? Look, maybe there's a reasonable take in there somewhere, but the way you put it just makes it sound like gibberish. It sounds like you're just hoping for either a dynamically typed language (eg. Python) or for a language which is fully type-inferred (eg. Haskell). Which way is it?
- auggierose 3y ago[flagged]
- deleted 3y ago[deleted]
- norir 3y agoThe article would have been stronger if it had benchmarks showing the performance improvements of this technique. My intuition is that the memory overhead of strings is not the main performance issue with most compilers.
- deleted 3y ago[deleted]
- chubot 3y agoYeah, for compilers, I would like to see a benchmark of small string optimization (which should be a huge win for most workloads) and string interning (also should be huge, not in the post though) A pet peeve is that benchmark suites often favor measuring performance with fibonacci or mandelbrot-type things, but string/graph/hash table workloads are much different, in multiple dimensions Compilers and network servers are more like the latter
- einpoklum 3y agoIs it not a better approach, when already assuming semi-niche usage, to rely on more information about the string? e.g. * Have some of your strings be guaranteed-memoized, then just pass an index into the global/thread-local array of memoized strings. * In tight loops working on a few strings, ensure they are all short, then forego pointers altogether and just use the values. etc.
- NooneAtAll3 3y agoI love how rust removed SSO from its string and now every library reimplements it over and over