16 ms·

“To be safe allocate 5 bytes more than you need”

274 points by luu 6y ago

floatingatoll 6y ago
UTF-8 characters can be composed of at most 4 bytes, plus a NUL terminator makes 5. I have no idea if this is true but it’s plausible enough for a Unicode parser!
- rurban 6y ago
  On the character level yes, but this is for strings, so looks totally broken to me.
  - rusk 6y ago
    The len is being passed to malloc which I recall takes number of bytes, so this explanation seems plausible. I very much doubt memory allocation is ”innacurate”, as per the comment ...
- SAI_Peregrinus 6y ago
  Not UTF-8 characters, UTF-8 code points. UTF-8 characters (more properly "extended grapheme clusters") can be of any length. " " is one character, 25 bytes long (0xf0,0x9f,0x91,0xa8,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa8,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa7,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa7) (it won't show correctly on HN, since HN strips some Unicode). If you assume that code point = character, your parser is buggy and doesn't comply with unicode specifications.
  - floatingatoll 6y ago
    I don’t presume to know enough about Unicode to code parsers it, but I’m happy to accept the correction!
  - zepearl 6y ago
    Uuuhh, this is an extremely important remark/correction for me, thank you. So far I was thinking as well that any "character" could be saved ("encoded"?) as UTF-8 by using max 4 bytes... .
    - floatingatoll 6y ago
      Any UTF-8 code point can be stored in 4 bytes or less, and so as long as you don’t care how many characters your string ends up displaying to the user or try to dissect the string by “characters” somehow, you’ll probably be fine; it’s just a series of valid UTF-8 code points that have meaning you don’t care about at your storage layer. If you’re tokenizing UTF-8 strings or trying to count “displayed” characters, then you also have to watch out for zalgo text that can use unlimited chains of code points and combiners to construct a single phrase out of potentially tens or hundreds of code points. Think it as a recursion limit of sorts. I feel that Unicode and cryptography share the aspect of “don’t try to write your own code to deal with it, because you’re certain to miss something important”.
      - zepearl 6y ago
        Thanks! I'll have to review my code... :P
  - anonymfus 6y ago
    > Not UTF-8 characters, UTF-8 code points. UTF-8 characters (more properly "extended grapheme clusters") can be of any length. Technically the only thing UTF-8 encodes is Unicode code points, as higher level abstractions like grapheme clusters are irrelevant for it. UTF-8 parser's job is to turn a sequence of octets to a sequence of code points. So-called "user-perceived characters" approximated as grapheme clusters is a relatively recent innovation in Unicode terminology. Compare the modern version of the spec (https://www.unicode.org/reports/tr29/ https://www.unicode.org/reports/tr29/) since Unicode 5.1.0 (2008): > It is important to recognize that what the user thinks of as a “character”—a basic unit of a writing system for a language—may not be just a single Unicode code point. Instead, that basic unit may be made up of multiple Unicode code points. To avoid ambiguity with the computer use of the term character, this is called a user-perceived character. For example, “G” + grave-accent is a user-perceived character: users think of it as a single character, yet is actually represented by two Unicode code points. These user-perceived characters are approximated by what is called a grapheme cluster, which can be determined programmatically. With the previous one (https://www.unicode.org/reports/tr29/tr29-11.html https://www.unicode.org/reports/tr29/tr29-11.html) from Unicode 5.0.0 (2006): > One or more Unicode characters may make up what the user thinks of as a character or basic unit of the language. To avoid ambiguity with the computer use of the term character, this is called a grapheme cluster. For example, “G” + acute-accent is a grapheme cluster: it is thought of as a single character by users, yet is actually represented by two Unicode code points. So you can notice "the computer use of the term character" in both. Notice also that these grave and acute accents used as examples existed in pre-Unicode encodings too, and we still call them "combining characters". Hence if we adhere to that old "computer use of the term character" then "UTF-8 characters" are Unicode code points, and "Unicode characters" don't exist; but if we use a modern colloquial meaning of characters as Unicode's "user-perceived characters" then "UTF-8 characters" don't exist.
  - Izkata 6y ago
    For those of us not fully in on the technical details, is your example basically invisible Zalgo Text, or is this something more subtle?
    - deleted 6y ago
      [deleted]
    - SAI_Peregrinus 6y ago
      It's a single emoji: "Family: Man, Man, Girl, Girl". Sequence is "Man, Zero-Width Joiner (ZWJ), Man, ZWJ, Girl, ZWJ, Girl". Picked because I looked up "Man" and "Girl" first, and just repeating the two is easy. https://emojipedia.org/family-man-man-girl-girl/ https://emojipedia.org/family-man-man-girl-girl/
deleted 6y ago
[deleted]
asveikau 6y ago
I don't recall where, but I remember once encountering an API that took a buffer and a length, and required the buffer to exceed the specified length by some n. Unlike this case, I think the requirement was documented. Still seemed like a recipe for bugs. If you need to implicitly adjust the length of the buffer upwards, it's not really the length of the buffer.
- Someone 6y ago
  Recipe for bugs but possibly also a recipe for performance. I’m not making any claims for this particular case, but if a function taking a large buffer to modify needs some extra space, and the code can get faster by storing that at the end of the buffer, requiring the caller to reserve that space can mean not having to copy the buffer twice, increasing memory use and execution time. A fairly common example is room for adding extra zero string terminators, so that an vectorized algorithm walking the input always hits one of them.
  - asveikau 6y ago
    I think there are better ways to encode that in API design that are less ambiguous. For example perhaps having a function or some other means to compute required buffer size, in a way that makes such padding requirements relatively opaque to the caller.
cbsks 6y ago
I abhor comments like these. It says that it needs to allocate 5 more bytes, and I can see that in the code, but it doesn't say why the magic number is 5. The comment explains the what but not the why. The commit message is equally as useless: https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d527cd4f1935eec3740d4d95a https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d5... What needs to be fixed so that this "+5" can be removed? What happens if something changes and the magic number needs to be 6? Also, where's the unit test?
- thaumasiotes 6y ago
  > Also, where's the unit test? What would you think if the following were true for a fairly generalized problem: - It is easy to prove a particular upper bound on memory requirements when calling a function. - It is very difficult to know exactly what the memory requirements will be for particular input. - No known input achieves the known upper bound. Is it a problem if we allocate enough memory to satisfy the bound we can prove, and then don't have a unit test showing we can't do with less?
  - pmiller2 6y ago
    If that's all the case, then, where's the proof? It might be "easy to prove," but it's probably not an "I can prove this trivially, on the fly" type of task.
  - cbsks 6y ago
    I'd be satisfied with that if I was a reviewer in the code review. I'd want that (and the proofs) explicitly mentioned in the comment, or at the very least in the commit message. At first glance the example seems contrived to me. Assuming that the code is deterministic, wouldn't it be trivial to measure the memory requirement for a particular input?
    - thaumasiotes 6y ago
      There are a lot of potential inputs.
avian 6y ago
Some more clues where this comes from are in this issue: https://github.com/DaveGamble/cJSON/issues/255 https://github.com/DaveGamble/cJSON/issues/255
- IshKebab 6y ago
  Pretty good advert for not writing code in C.
  - GuB-42 6y ago
    More like writing C properly. When you program in C, you should know exactly what each byte of memory is for. If you don't do that, not only you will eventually get crashes and leaks and overflows, but you also miss the point of programming in C in the first place. C is fast, but C is not fast because it overclocks your CPU or whatever magic you can think of. An good reason why is is fast is that it gives you tight control over your memory. You can reuse buffers, size them precisely, allocate them exactly when you need them and free them when you are finished, nothing funny happening behind your back. It generally results in lower memory usage, better use of cache and therefore better performance. If you don't manage your memory precisely, then sure, C is probably not the language for you.
    - harry8 6y ago
      >If you don't manage your memory precisely, then sure, C is probably not the language for you. I agree with everything above that line and probably the intent of that line too. However I'd phrase it as: If you don't want to be forced to make a large effort managing memory for the given task, C is the wrong tool for that job. Even when you're great with C. Even when C is wonderful for a different job because you do it fabulously well. I use C and like it. I don't use it when python is good enough for the job because in those situations python is likely to be actually better than C because you'd incur a debt to pay for something you don't need and as a result you just might miss one of those payments. The interest rate on a missed payment can get pretty steep. Prefer shell, ruby, perl, something jvm, whatever? - Great. Exactly the same point applies. I'm sure this point does /not/ apply to your comment above but it could be (mis)interepreted that way - C programming macho arrogance is not helpful for good quality software. C macho arrogance is pretty destructive, in fact and IMHO the worst thing about the use C (& C++ etc.)
29athrowaway 6y ago
Looks like a workaround rather than a fix, for whatever problem they were having. This happens in science too. Many constants are placeholders for stuff we do not understand.
- pantalaimon 6y ago
  But science is a bit like reverse engineering the universe. In this case however they wrote the source code.
- alerighi 6y ago
  Despite the (horrible) name computer science, informatics is not science, is math. There is a big difference: in science you observe and try to understand something that already exists, the universe. In math (and informatics) you build your own universe with your set of rules. It means that you can and should understand everything (well, of course if you assume the hardware works perfectly as specified).
  - MaxBarraclough 6y ago
    Computer science is not entirely math. Compilers, for instance, care about real-world performance, not theory. Physics is more mathematical than computer science, but there's no doubt that physics is a science.
  - 29athrowaway 6y ago
    Discrete math, computer science, etc. are sciences (although some people claim math is not a science... that's a discussion for another day). Software engineering, like all forms of engineering, is applied science plus processes based on empirical evidence.
    - MaxBarraclough 6y ago
      > Discrete math, computer science, etc. are sciences (although some people claim math is not a science I was surprised to see that, at least according to Wikipedia, opinions (of people of consequence) vary on this point. [0] Seems to me perfectly clear that math is not a science, as it's not empirical, but this doesn't seem to be universally agreed upon. [0] https://en.wikipedia.org/wiki/Mathematics#Mathematics_as_science https://en.wikipedia.org/wiki/Mathematics#Mathematics_as_sci...
asdfasgasdgasdg 6y ago
We have a kind of varint-based delta decoder at work that can read up to 15 bytes past the end of its buffer, because it uses uint64s to read the buffer faster, than the buffer doesn't encode byte-length information. Since it doesn't know how many bits wide the last entry will be, and since it reads ahead a little, it can end up 16 bytes starting at the last byte and proceeding 15 bytes onward. It doesn't matter that these bytes are filled with garbage, because a well formed program will only use the bits from one of the valid bytes. The outer code knows how many entries to look for, so it just calls the advance function the correct number of times, and those bits past the end don't get used. This can lead to a pretty subtle crash because, except in msan mode, reading those fifteen bytes won't cause any problem except at the page boundary. This is because you don't corrupt the sentinel bytes, since they're never written. So to detect the bug you either have to run the code in debug mode (which we rarely do, because the code is deep inside a very expensive database system), or you have to get unlucky. I tried fixing this, but adding a "past the end" test really hurt performance. Instead, we continued with the preexisting solution: copy the data into a buffer fifteen bytes longer than the data, then decode it. T_T
- pedrocr 6y ago
  The same is done for decoding camera raw formats. Variable encoding of the number of bits in the stream means you never know when the decode will end. Reading all the file into a buffer longer than needed is fast, whereas the bit pump is performance critical and having to check for end of buffer every time you want to read would be painful.
  - asdfasgasdgasdg 6y ago
    Saddest thing is we're reading these values from a database, and the database SDK does not have a mechanism for reading values into user-controlled buffers without copying. That is a conceptually neat solution to the problem, but since it's a somewhat strange thing to want to do, we can't do it in our case. Storing the extended values is something I also considered, but there are tens or hundreds of billions of them in production. Couldn't really ask for an extra PB of space for the relatively small performance and elegance benefit you get from not copying these things.
SamReidHughes 6y ago
I've used cJSON. Its problems have been far deeper and more serious than this.
- pantalaimon 6y ago
  Did you try jsmn?
  - SamReidHughes 6y ago
    No, but I haven't personally done a search of C/C++ JSON libraries.
dls2016 6y ago
Haha I just used this code. My little ESP32 data acquisition project has been running two days since switching to the PrintPreallocate function with essentially constant memory usage so ¯\_(ツ)_/¯. Way too many other things to worry about.
- elcritch 6y ago
  Exactly, if their inputs are fairly well known and tested, adding 5 magic bytes is hackish but effective. It could take days or weeks to debug that properly, if at all. Nice you were able to get constant memory. I was getting 40byte max memory usage difference between identical RPC calls on the esp32, but that seems due to Nim’s ARC garbage collector. Sometimes +20 bytes, sometimes -20 bytes but not leaking. Though maybe it’s an esp-idf thing. Took me a bit to just call it good and focus on more important things. ¯\_(ツ)_/¯
DannyB2 6y ago
5 bytes? What about 5 characters? When I started almost four decades ago it was then true that bytes and characters were the same thing.
- aYsY4dDQ2NrcNzA 6y ago
  I don’t think that was guaranteed, at least not in C. Wasn’t that implementation-dependent?
  - MereInterest 6y ago
    Sort of, yeah. In C, the size of the integer primitives isn't defined. What is defined is that sizeof(char) will always be 1 (one). However, it is entirely implementation defined what that 1 refers to. On most systems, it is the number of 8-bit bytes, but it could refer to a larger or smaller amount of memory.
    - wahern 6y ago
      > but it could refer to a larger or smaller amount of memory. Never smaller as the minimum limits for char require at least 8 bits. But definitely can be wider than 8 bits, as is common on DSPs or some old mainframes. Though, even on systems that don't permit direct addressing of 8-bit char, C implementations will sometimes emulate it. FWIW, POSIX mandates a fixed, 8-bit char.
    - bnegreve 6y ago
      > However, it is entirely implementation defined what that 1 refers to. Not entirely, there is a vague description of what a byte should be able to represent. The C and C++ programming languages define byte as an "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment" https://en.wikipedia.org/wiki/Byte https://en.wikipedia.org/wiki/Byte
- lambda_obrien 6y ago
  That's no longer true, in case you were wondering. People still say `bytes <-"instead of"-> chars` sometimes but we should stop that.
gfodor 6y ago
I was going to trash this, but it actually made me think of something non-obvious: where is the line between hacks like this and smart behavior? For example, we have code in systems that performs network retries, and I have code in my own software that performs polling operations when a request/response "should" work, but in practice, a variety of reasons cause it to be less robust. It seems right that something like "allocating extra memory just to be safe" falls on the wrong side of defensive programming vs obvious kludge, but where is the line, exactly? It doesn't seem to be first vs third party code. Is it network hops? That seems extremely arbitrary, especially given that modern networking has characteristics closer to a bus than say, accessing a disk, where such defensiveness is less sane. If network boundaries are the norm where we start assuming failure is likely, maybe that's why microservices are considered beneficial since they result in more defensive programming in practice even though in principle there's no reason that needs to be the boundary? Maybe I've had too much coffee this morning.
- deleted 6y ago
  [deleted]
- zamadatix 6y ago
  Depends what you call smart behaviour I suppose. For the vast majority of projects though I'd assume the following to be smart behaviour: - Is it robust - Is it fast (enough) - Is it the simplest way to achieve those levels of robustness and speed If the answer to the first 2 is largely "yes" and the 3rd is "no" then I'd call it a bad hack. OTOH if the answer to 3 is also "yes" then it's a good hack. If the answer to 1 or 2 is "no" then it's not ready to ship. In either case a comment saying "this is the simple/safe way, performance opportunity via..." Or "this is the complicated way because <reasons complicated way was needed, usually perf> and it this is why it works..." is good to leave in case performance requirements ever change or someone is trying to figure out why you went the way you did.
- kansface 6y ago
  > For example, we have code in systems that performs network retries, and I have code in my own software that performs polling operations when a request/response "should" work, but in practice, a variety of reasons cause it to be less robust. Apples and oranges. The network is unreliable and all code dealing with the network should treat it as such. The file system and disks are also unreliable, but are probably more reliable by a factor of 10K than the network. Engineers mostly choose to ignore these potential errors via unintentional decisions or do stuff like let the process crash because restarting an API server once a year doesn't matter. Of course, not everyone has that luxury. Determining how much memory to allocate ought to be perfectly deterministic which is why this is such a code smell. > where is the line, exactly? The line to me is pretty clear in this case! There are all sorts of reasons why this code would be acceptable: if fixing the code to prevent the bug[s] is sufficiently onerous as to cause more bugs than the fix would prevent, or is so much work that it would never be undertaken, or so complex that the code is un-mergable, an emergency hot fix... all acceptable so long as the code is documented as such. In other words, the line crossed here was in the comment. Where did the number 5 come from? Where's the link to an issue tracking memory allocation/estimation? I believe most comments in code are worse than useless - that we shouldn't merely document bad code, but write code that is so blindingly obvious and idiomatic that comments detract from its perfection. Comments exist when we deviate from the platonic ideal — the real world with leaky abstractions, deadlines, bugs and dollars.
SilasX 6y ago
Related: There was that story about how axle count on Swiss trains can't be a multiple of 256 (2^8) [0], and a comment mentioned that German has a limit of 252 "just to be safe": https://news.ycombinator.com/item?id=12071686 https://news.ycombinator.com/item?id=12071686 [0] Because there are only 8 bits to store the axle counter for whether the train has passed, and you don't want overflow to zero.
- jbay808 6y ago
  That's interesting! But a safety factor does make sense here if you're worried about a small probability of double-counting an axle.
  - Doxin 6y ago
    Double counting an axle is a critical failure for an axle counter. It could keep a track section blocked until someone comes to fix the axle counter. Even worse it could unblock a track section while there's still (part of) a train on it. If you're worried about double-counting an axle you probably need to design your axle counters better.
- cleansingfire 6y ago
  Sounds like Swiss trains need a single axle connector to ensure all trains have an odd number of axles.
  - skykooler 6y ago
    Or use seven axle locomotives. (Did a bit of research, at least one has existed: http://cs.trains.com/trn/f/111/t/72627.aspx http://cs.trains.com/trn/f/111/t/72627.aspx)
    - jcranmer 6y ago
      Broadly speaking, with electric drive, it generally makes the most sense to have both your four and aft bogies as all-drive axles, and there's no real compelling reason to have those axles be different. In practice, this means that the vast, vast majority of modern locomotives are B-B or C-C (2-axle/3-axle bogies, respectively), with B-B-B (3 2-axle bogies) probably the next most common. Other configurations are almost entirely experimental or one-off locomotive configurations. In the steam era, things were rather different. Steam power requires a linkage of rather large drive wheels, which generally means you need unpowered leading and trailing wheelsets for stability and performance purposes. The trailing wheels are almost purely to support the weight on the back end of the locomotive, but leading wheels also help with curves in addition to supporting weight on the front end. Single leading axles were quite common in the steam era, with 2-8-0 being perhaps the single most common arrangement.
alphagrep12345 6y ago
This happened at my previous work place. They added 1 free byte every time they saved some data to disk. When I asked my manager about it, he said - ' There was a crash a while ago and this fixed it. No one knows why, but this is what we all do after that'
- comboy 6y ago
  There are so many IT companies craving for coders, just saying.
  - alphagrep12345 6y ago
    Haha. 'Previous' work place :)
spaetzleesser 6y ago
Wouldn’t you wrap the allocation with an alloc/free function that does the allocation with whatever extra bytes that are needed? Letting the API users deal with such details seems a recipe for disaster.
- zelly 6y ago
  Because then you're forcing clients to use malloc rather than their own allocator
  - spaetzleesser 6y ago
    Good point
ExcavateGrandMa 6y ago
hmmmm... That's kind of a bean counter. krkRKRkrkrkrkRKR
PixelOfDeath 6y ago
x86_64 malloc already uses 16 byte alignment and portions to support SSE commands. So why not go all the way and allocate full cache lines? This also prevents accidental false sharing between different malloc pointers.
WalterBright 6y ago
This screams "time for a serious code review" to me. Also use an array type that does overflow checking.
ajarmst 6y ago
Were it my team, this would get bounced with a request for a link to the bug-report/documentation in cJSON that necessitates this wart and at least a FIXME flag so that we periodically re-visit the 'why does cJSON still not correctly estimate its memory and if it can't then why the hell is it not returning the minimum safe value rather than a guess?' unsightly hack in our beautiful code.
quelsolaar 6y ago
Over allocating is often a very useful strategy. I wrote a fast Json parser a while ago and one of the largest optimizations was to look at the size of the file, compute the worst case of how much memory it would need, and then do one allocation and then use the memory. Another example would be a dynamic list of values. If you use a linked list, and have 64bit pointer and a 64bit value, each link costs 16 bytes. If you have a list of say 8 values then that's 8 allocations and 16*8 = 128 bytes. If you instead allocate speculatively an array of 16 values also taking 128 bytes, and then only use 8 of the values, you only need one allocation. If the number of values you need grows beyond 16, you need to reallocate, and expensive operation, but compared to making one allocation each time a value is added its much faster. Also all values are close to each other in memory so cache coherence will be much better, and you may end up with an order of magnitude faster access. This can be true even if you do expensive operations like insert. Yes, you can improve the performance of a liked list by allocating lots of links in one allocation, but the added space of the pointers, and the out of order access will still cost you. Obviously, when you do this you should provide functions that always allocate the right number for the user of the code so that there is no magic numbers visible to the end user....
- hzhou321 6y ago
  > Over allocating is often a very useful strategy. It is not! * If you know exact reasons and exact how much space need (over) allocate, then you should document the reason, and it is no long over allocating. * If you don't know the exact reasons and only know once a while it requires additional space, then you are not solving the problem. You are kicking the can down the road, and it is likely to explode later, possibly with inappropriate timing. * If you know exactly how much the space you need, then the over allocating is just misleading code. Fix Your Code! EDIT: Your comment apparently is for something else. Anyway, the headline needs some counter correction.
  - quelsolaar 6y ago
    I'm talking about internal code that is not exposed to the user. There are loads of situations where something will fluctuate in size rapidly, you dont know beforehand to what extent, and allocating memory every-time it changes is very inefficient. In these cases speculatively over allocating is a very good strategy.
sagarm 6y ago
I've written APIs that require extra bytes. The exact requirements can be complex to explain, so to minimize complexity I would just put the maximum over-buffer size in the function docs. As for _why_: knowing that you have a buffer of at least a certain size can allow you to avoid bounds checks, branches, and allocations. For hot loops this can result in a significant performance improvement.
not2b 6y ago
That's a setup for something that used to be a common interview question: how to extend a dynamic string or vector when you need to grow the allocation. If you allocate a fixed amount of excess (say, 5 bytes) when you need to grow the string, then repeatedly appending to your string or vector has quadratic cost. And an early version of Microsoft Foundation Classes (pre-STL, from the 80s) had this bug in the string class.
johnnujler 6y ago
The best way to be safe is to fail loud and clear, and definitely do not surprise your users who only use the api and don’t actually read the source code or how it is implemented.
junon 6y ago
This is somewhat common in branchless parsers. You need a few more bytes at the end of the sequence in order to allow efficient reads to take place. This isn't uncommon, and is why it's pretty important that performance-critical software also RTFM.
FSMaxB 6y ago
My statement: https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d527cd4f1935eec3740d4d95a#commitcomment-44482553 https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d5... At some point I have realised, that just letting cJSON be the horror of a codebase it was before I started maintaining it would have been the best thing to do, but that's what you call hindsight. At least now I know. One reason I burned out was because I felt horrified by how many people are using cJSON and felt a responsibility to make it better and safer for all of them, even though I myself haven't ever been really using it. The combination of this mounting pressure plus the the impossible fight against semantic versioning and memory unsafety gave me the rest. By improving it, but being unable to completely "fix" it, I probably led more people to use it, making the situation even worse than it was before.
sbrki 6y ago
Does anyone know which font is that?
wunderbaba 6y ago
This should be called the "Baker's Dozen" law for engineering.

274 points by luu 6y ago

UTF-8 characters can be composed of at most 4 bytes, plus a NUL terminator makes 5. I have no idea if this is true but it’s plausible enough for a Unicode parser!

rurban 6y ago
On the character level yes, but this is for strings, so looks totally broken to me.
- rusk 6y ago
  The len is being passed to malloc which I recall takes number of bytes, so this explanation seems plausible. I very much doubt memory allocation is ”innacurate”, as per the comment ...
SAI_Peregrinus 6y ago
Not UTF-8 characters, UTF-8 code points. UTF-8 characters (more properly "extended grapheme clusters") can be of any length. " " is one character, 25 bytes long (0xf0,0x9f,0x91,0xa8,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa8,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa7,0xe2,0x80,0x8d,0xf0,0x9f,0x91,0xa7) (it won't show correctly on HN, since HN strips some Unicode). If you assume that code point = character, your parser is buggy and doesn't comply with unicode specifications.
- floatingatoll 6y ago
  I don’t presume to know enough about Unicode to code parsers it, but I’m happy to accept the correction!
- zepearl 6y ago
  Uuuhh, this is an extremely important remark/correction for me, thank you. So far I was thinking as well that any "character" could be saved ("encoded"?) as UTF-8 by using max 4 bytes... .
  - floatingatoll 6y ago
    Any UTF-8 code point can be stored in 4 bytes or less, and so as long as you don’t care how many characters your string ends up displaying to the user or try to dissect the string by “characters” somehow, you’ll probably be fine; it’s just a series of valid UTF-8 code points that have meaning you don’t care about at your storage layer. If you’re tokenizing UTF-8 strings or trying to count “displayed” characters, then you also have to watch out for zalgo text that can use unlimited chains of code points and combiners to construct a single phrase out of potentially tens or hundreds of code points. Think it as a recursion limit of sorts. I feel that Unicode and cryptography share the aspect of “don’t try to write your own code to deal with it, because you’re certain to miss something important”.
    - zepearl 6y ago
      Thanks! I'll have to review my code... :P
- anonymfus 6y ago
  > Not UTF-8 characters, UTF-8 code points. UTF-8 characters (more properly "extended grapheme clusters") can be of any length. Technically the only thing UTF-8 encodes is Unicode code points, as higher level abstractions like grapheme clusters are irrelevant for it. UTF-8 parser's job is to turn a sequence of octets to a sequence of code points. So-called "user-perceived characters" approximated as grapheme clusters is a relatively recent innovation in Unicode terminology. Compare the modern version of the spec (https://www.unicode.org/reports/tr29/ https://www.unicode.org/reports/tr29/) since Unicode 5.1.0 (2008): > It is important to recognize that what the user thinks of as a “character”—a basic unit of a writing system for a language—may not be just a single Unicode code point. Instead, that basic unit may be made up of multiple Unicode code points. To avoid ambiguity with the computer use of the term character, this is called a user-perceived character. For example, “G” + grave-accent is a user-perceived character: users think of it as a single character, yet is actually represented by two Unicode code points. These user-perceived characters are approximated by what is called a grapheme cluster, which can be determined programmatically. With the previous one (https://www.unicode.org/reports/tr29/tr29-11.html https://www.unicode.org/reports/tr29/tr29-11.html) from Unicode 5.0.0 (2006): > One or more Unicode characters may make up what the user thinks of as a character or basic unit of the language. To avoid ambiguity with the computer use of the term character, this is called a grapheme cluster. For example, “G” + acute-accent is a grapheme cluster: it is thought of as a single character by users, yet is actually represented by two Unicode code points. So you can notice "the computer use of the term character" in both. Notice also that these grave and acute accents used as examples existed in pre-Unicode encodings too, and we still call them "combining characters". Hence if we adhere to that old "computer use of the term character" then "UTF-8 characters" are Unicode code points, and "Unicode characters" don't exist; but if we use a modern colloquial meaning of characters as Unicode's "user-perceived characters" then "UTF-8 characters" don't exist.
- Izkata 6y ago
  For those of us not fully in on the technical details, is your example basically invisible Zalgo Text, or is this something more subtle?
  - deleted 6y ago
    [deleted]
  - SAI_Peregrinus 6y ago
    It's a single emoji: "Family: Man, Man, Girl, Girl". Sequence is "Man, Zero-Width Joiner (ZWJ), Man, ZWJ, Girl, ZWJ, Girl". Picked because I looked up "Man" and "Girl" first, and just repeating the two is easy. https://emojipedia.org/family-man-man-girl-girl/ https://emojipedia.org/family-man-man-girl-girl/

deleted 6y ago

[deleted]

asveikau 6y ago

I don't recall where, but I remember once encountering an API that took a buffer and a length, and required the buffer to exceed the specified length by some n. Unlike this case, I think the requirement was documented. Still seemed like a recipe for bugs. If you need to implicitly adjust the length of the buffer upwards, it's not really the length of the buffer.

Someone 6y ago
Recipe for bugs but possibly also a recipe for performance. I’m not making any claims for this particular case, but if a function taking a large buffer to modify needs some extra space, and the code can get faster by storing that at the end of the buffer, requiring the caller to reserve that space can mean not having to copy the buffer twice, increasing memory use and execution time. A fairly common example is room for adding extra zero string terminators, so that an vectorized algorithm walking the input always hits one of them.
- asveikau 6y ago
  I think there are better ways to encode that in API design that are less ambiguous. For example perhaps having a function or some other means to compute required buffer size, in a way that makes such padding requirements relatively opaque to the caller.

cbsks 6y ago

I abhor comments like these. It says that it needs to allocate 5 more bytes, and I can see that in the code, but it doesn't say why the magic number is 5. The comment explains the what but not the why. The commit message is equally as useless: https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d527cd4f1935eec3740d4d95a https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d5... What needs to be fixed so that this "+5" can be removed? What happens if something changes and the magic number needs to be 6? Also, where's the unit test?

thaumasiotes 6y ago
> Also, where's the unit test? What would you think if the following were true for a fairly generalized problem: - It is easy to prove a particular upper bound on memory requirements when calling a function. - It is very difficult to know exactly what the memory requirements will be for particular input. - No known input achieves the known upper bound. Is it a problem if we allocate enough memory to satisfy the bound we can prove, and then don't have a unit test showing we can't do with less?
- pmiller2 6y ago
  If that's all the case, then, where's the proof? It might be "easy to prove," but it's probably not an "I can prove this trivially, on the fly" type of task.
- cbsks 6y ago
  I'd be satisfied with that if I was a reviewer in the code review. I'd want that (and the proofs) explicitly mentioned in the comment, or at the very least in the commit message. At first glance the example seems contrived to me. Assuming that the code is deterministic, wouldn't it be trivial to measure the memory requirement for a particular input?
  - thaumasiotes 6y ago
    There are a lot of potential inputs.

avian 6y ago

Some more clues where this comes from are in this issue: https://github.com/DaveGamble/cJSON/issues/255 https://github.com/DaveGamble/cJSON/issues/255

IshKebab 6y ago
Pretty good advert for not writing code in C.
- GuB-42 6y ago
  More like writing C properly. When you program in C, you should know exactly what each byte of memory is for. If you don't do that, not only you will eventually get crashes and leaks and overflows, but you also miss the point of programming in C in the first place. C is fast, but C is not fast because it overclocks your CPU or whatever magic you can think of. An good reason why is is fast is that it gives you tight control over your memory. You can reuse buffers, size them precisely, allocate them exactly when you need them and free them when you are finished, nothing funny happening behind your back. It generally results in lower memory usage, better use of cache and therefore better performance. If you don't manage your memory precisely, then sure, C is probably not the language for you.
  - harry8 6y ago
    >If you don't manage your memory precisely, then sure, C is probably not the language for you. I agree with everything above that line and probably the intent of that line too. However I'd phrase it as: If you don't want to be forced to make a large effort managing memory for the given task, C is the wrong tool for that job. Even when you're great with C. Even when C is wonderful for a different job because you do it fabulously well. I use C and like it. I don't use it when python is good enough for the job because in those situations python is likely to be actually better than C because you'd incur a debt to pay for something you don't need and as a result you just might miss one of those payments. The interest rate on a missed payment can get pretty steep. Prefer shell, ruby, perl, something jvm, whatever? - Great. Exactly the same point applies. I'm sure this point does /not/ apply to your comment above but it could be (mis)interepreted that way - C programming macho arrogance is not helpful for good quality software. C macho arrogance is pretty destructive, in fact and IMHO the worst thing about the use C (& C++ etc.)

29athrowaway 6y ago

Looks like a workaround rather than a fix, for whatever problem they were having. This happens in science too. Many constants are placeholders for stuff we do not understand.

pantalaimon 6y ago
But science is a bit like reverse engineering the universe. In this case however they wrote the source code.
alerighi 6y ago
Despite the (horrible) name computer science, informatics is not science, is math. There is a big difference: in science you observe and try to understand something that already exists, the universe. In math (and informatics) you build your own universe with your set of rules. It means that you can and should understand everything (well, of course if you assume the hardware works perfectly as specified).
- MaxBarraclough 6y ago
  Computer science is not entirely math. Compilers, for instance, care about real-world performance, not theory. Physics is more mathematical than computer science, but there's no doubt that physics is a science.
- 29athrowaway 6y ago
  Discrete math, computer science, etc. are sciences (although some people claim math is not a science... that's a discussion for another day). Software engineering, like all forms of engineering, is applied science plus processes based on empirical evidence.
  - MaxBarraclough 6y ago
    > Discrete math, computer science, etc. are sciences (although some people claim math is not a science I was surprised to see that, at least according to Wikipedia, opinions (of people of consequence) vary on this point. [0] Seems to me perfectly clear that math is not a science, as it's not empirical, but this doesn't seem to be universally agreed upon. [0] https://en.wikipedia.org/wiki/Mathematics#Mathematics_as_science https://en.wikipedia.org/wiki/Mathematics#Mathematics_as_sci...

asdfasgasdgasdg 6y ago

We have a kind of varint-based delta decoder at work that can read up to 15 bytes past the end of its buffer, because it uses uint64s to read the buffer faster, than the buffer doesn't encode byte-length information. Since it doesn't know how many bits wide the last entry will be, and since it reads ahead a little, it can end up 16 bytes starting at the last byte and proceeding 15 bytes onward. It doesn't matter that these bytes are filled with garbage, because a well formed program will only use the bits from one of the valid bytes. The outer code knows how many entries to look for, so it just calls the advance function the correct number of times, and those bits past the end don't get used. This can lead to a pretty subtle crash because, except in msan mode, reading those fifteen bytes won't cause any problem except at the page boundary. This is because you don't corrupt the sentinel bytes, since they're never written. So to detect the bug you either have to run the code in debug mode (which we rarely do, because the code is deep inside a very expensive database system), or you have to get unlucky. I tried fixing this, but adding a "past the end" test really hurt performance. Instead, we continued with the preexisting solution: copy the data into a buffer fifteen bytes longer than the data, then decode it. T_T

pedrocr 6y ago
The same is done for decoding camera raw formats. Variable encoding of the number of bits in the stream means you never know when the decode will end. Reading all the file into a buffer longer than needed is fast, whereas the bit pump is performance critical and having to check for end of buffer every time you want to read would be painful.
- asdfasgasdgasdg 6y ago
  Saddest thing is we're reading these values from a database, and the database SDK does not have a mechanism for reading values into user-controlled buffers without copying. That is a conceptually neat solution to the problem, but since it's a somewhat strange thing to want to do, we can't do it in our case. Storing the extended values is something I also considered, but there are tens or hundreds of billions of them in production. Couldn't really ask for an extra PB of space for the relatively small performance and elegance benefit you get from not copying these things.

SamReidHughes 6y ago

I've used cJSON. Its problems have been far deeper and more serious than this.

pantalaimon 6y ago
Did you try jsmn?
- SamReidHughes 6y ago
  No, but I haven't personally done a search of C/C++ JSON libraries.

dls2016 6y ago

Haha I just used this code. My little ESP32 data acquisition project has been running two days since switching to the PrintPreallocate function with essentially constant memory usage so ¯\_(ツ)_/¯. Way too many other things to worry about.

elcritch 6y ago
Exactly, if their inputs are fairly well known and tested, adding 5 magic bytes is hackish but effective. It could take days or weeks to debug that properly, if at all. Nice you were able to get constant memory. I was getting 40byte max memory usage difference between identical RPC calls on the esp32, but that seems due to Nim’s ARC garbage collector. Sometimes +20 bytes, sometimes -20 bytes but not leaking. Though maybe it’s an esp-idf thing. Took me a bit to just call it good and focus on more important things. ¯\_(ツ)_/¯

DannyB2 6y ago

5 bytes? What about 5 characters? When I started almost four decades ago it was then true that bytes and characters were the same thing.

aYsY4dDQ2NrcNzA 6y ago
I don’t think that was guaranteed, at least not in C. Wasn’t that implementation-dependent?
- MereInterest 6y ago
  Sort of, yeah. In C, the size of the integer primitives isn't defined. What is defined is that sizeof(char) will always be 1 (one). However, it is entirely implementation defined what that 1 refers to. On most systems, it is the number of 8-bit bytes, but it could refer to a larger or smaller amount of memory.
  - wahern 6y ago
    > but it could refer to a larger or smaller amount of memory. Never smaller as the minimum limits for char require at least 8 bits. But definitely can be wider than 8 bits, as is common on DSPs or some old mainframes. Though, even on systems that don't permit direct addressing of 8-bit char, C implementations will sometimes emulate it. FWIW, POSIX mandates a fixed, 8-bit char.
  - bnegreve 6y ago
    > However, it is entirely implementation defined what that 1 refers to. Not entirely, there is a vague description of what a byte should be able to represent. The C and C++ programming languages define byte as an "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment" https://en.wikipedia.org/wiki/Byte https://en.wikipedia.org/wiki/Byte
lambda_obrien 6y ago
That's no longer true, in case you were wondering. People still say `bytes <-"instead of"-> chars` sometimes but we should stop that.

gfodor 6y ago

I was going to trash this, but it actually made me think of something non-obvious: where is the line between hacks like this and smart behavior? For example, we have code in systems that performs network retries, and I have code in my own software that performs polling operations when a request/response "should" work, but in practice, a variety of reasons cause it to be less robust. It seems right that something like "allocating extra memory just to be safe" falls on the wrong side of defensive programming vs obvious kludge, but where is the line, exactly? It doesn't seem to be first vs third party code. Is it network hops? That seems extremely arbitrary, especially given that modern networking has characteristics closer to a bus than say, accessing a disk, where such defensiveness is less sane. If network boundaries are the norm where we start assuming failure is likely, maybe that's why microservices are considered beneficial since they result in more defensive programming in practice even though in principle there's no reason that needs to be the boundary? Maybe I've had too much coffee this morning.

deleted 6y ago
[deleted]
zamadatix 6y ago
Depends what you call smart behaviour I suppose. For the vast majority of projects though I'd assume the following to be smart behaviour: - Is it robust - Is it fast (enough) - Is it the simplest way to achieve those levels of robustness and speed If the answer to the first 2 is largely "yes" and the 3rd is "no" then I'd call it a bad hack. OTOH if the answer to 3 is also "yes" then it's a good hack. If the answer to 1 or 2 is "no" then it's not ready to ship. In either case a comment saying "this is the simple/safe way, performance opportunity via..." Or "this is the complicated way because <reasons complicated way was needed, usually perf> and it this is why it works..." is good to leave in case performance requirements ever change or someone is trying to figure out why you went the way you did.
kansface 6y ago
> For example, we have code in systems that performs network retries, and I have code in my own software that performs polling operations when a request/response "should" work, but in practice, a variety of reasons cause it to be less robust. Apples and oranges. The network is unreliable and all code dealing with the network should treat it as such. The file system and disks are also unreliable, but are probably more reliable by a factor of 10K than the network. Engineers mostly choose to ignore these potential errors via unintentional decisions or do stuff like let the process crash because restarting an API server once a year doesn't matter. Of course, not everyone has that luxury. Determining how much memory to allocate ought to be perfectly deterministic which is why this is such a code smell. > where is the line, exactly? The line to me is pretty clear in this case! There are all sorts of reasons why this code would be acceptable: if fixing the code to prevent the bug[s] is sufficiently onerous as to cause more bugs than the fix would prevent, or is so much work that it would never be undertaken, or so complex that the code is un-mergable, an emergency hot fix... all acceptable so long as the code is documented as such. In other words, the line crossed here was in the comment. Where did the number 5 come from? Where's the link to an issue tracking memory allocation/estimation? I believe most comments in code are worse than useless - that we shouldn't merely document bad code, but write code that is so blindingly obvious and idiomatic that comments detract from its perfection. Comments exist when we deviate from the platonic ideal — the real world with leaky abstractions, deadlines, bugs and dollars.

SilasX 6y ago

Related: There was that story about how axle count on Swiss trains can't be a multiple of 256 (2^8) [0], and a comment mentioned that German has a limit of 252 "just to be safe": https://news.ycombinator.com/item?id=12071686 https://news.ycombinator.com/item?id=12071686 [0] Because there are only 8 bits to store the axle counter for whether the train has passed, and you don't want overflow to zero.

jbay808 6y ago
That's interesting! But a safety factor does make sense here if you're worried about a small probability of double-counting an axle.
- Doxin 6y ago
  Double counting an axle is a critical failure for an axle counter. It could keep a track section blocked until someone comes to fix the axle counter. Even worse it could unblock a track section while there's still (part of) a train on it. If you're worried about double-counting an axle you probably need to design your axle counters better.
cleansingfire 6y ago
Sounds like Swiss trains need a single axle connector to ensure all trains have an odd number of axles.
- skykooler 6y ago
  Or use seven axle locomotives. (Did a bit of research, at least one has existed: http://cs.trains.com/trn/f/111/t/72627.aspx http://cs.trains.com/trn/f/111/t/72627.aspx)
  - jcranmer 6y ago
    Broadly speaking, with electric drive, it generally makes the most sense to have both your four and aft bogies as all-drive axles, and there's no real compelling reason to have those axles be different. In practice, this means that the vast, vast majority of modern locomotives are B-B or C-C (2-axle/3-axle bogies, respectively), with B-B-B (3 2-axle bogies) probably the next most common. Other configurations are almost entirely experimental or one-off locomotive configurations. In the steam era, things were rather different. Steam power requires a linkage of rather large drive wheels, which generally means you need unpowered leading and trailing wheelsets for stability and performance purposes. The trailing wheels are almost purely to support the weight on the back end of the locomotive, but leading wheels also help with curves in addition to supporting weight on the front end. Single leading axles were quite common in the steam era, with 2-8-0 being perhaps the single most common arrangement.

alphagrep12345 6y ago

This happened at my previous work place. They added 1 free byte every time they saved some data to disk. When I asked my manager about it, he said - ' There was a crash a while ago and this fixed it. No one knows why, but this is what we all do after that'

comboy 6y ago
There are so many IT companies craving for coders, just saying.
- alphagrep12345 6y ago
  Haha. 'Previous' work place :)

spaetzleesser 6y ago

Wouldn’t you wrap the allocation with an alloc/free function that does the allocation with whatever extra bytes that are needed? Letting the API users deal with such details seems a recipe for disaster.

zelly 6y ago
Because then you're forcing clients to use malloc rather than their own allocator
- spaetzleesser 6y ago
  Good point

ExcavateGrandMa 6y ago

hmmmm... That's kind of a bean counter. krkRKRkrkrkrkRKR

PixelOfDeath 6y ago

x86_64 malloc already uses 16 byte alignment and portions to support SSE commands. So why not go all the way and allocate full cache lines? This also prevents accidental false sharing between different malloc pointers.

WalterBright 6y ago

This screams "time for a serious code review" to me. Also use an array type that does overflow checking.

ajarmst 6y ago

Were it my team, this would get bounced with a request for a link to the bug-report/documentation in cJSON that necessitates this wart and at least a FIXME flag so that we periodically re-visit the 'why does cJSON still not correctly estimate its memory and if it can't then why the hell is it not returning the minimum safe value rather than a guess?' unsightly hack in our beautiful code.

quelsolaar 6y ago

Over allocating is often a very useful strategy. I wrote a fast Json parser a while ago and one of the largest optimizations was to look at the size of the file, compute the worst case of how much memory it would need, and then do one allocation and then use the memory. Another example would be a dynamic list of values. If you use a linked list, and have 64bit pointer and a 64bit value, each link costs 16 bytes. If you have a list of say 8 values then that's 8 allocations and 16*8 = 128 bytes. If you instead allocate speculatively an array of 16 values also taking 128 bytes, and then only use 8 of the values, you only need one allocation. If the number of values you need grows beyond 16, you need to reallocate, and expensive operation, but compared to making one allocation each time a value is added its much faster. Also all values are close to each other in memory so cache coherence will be much better, and you may end up with an order of magnitude faster access. This can be true even if you do expensive operations like insert. Yes, you can improve the performance of a liked list by allocating lots of links in one allocation, but the added space of the pointers, and the out of order access will still cost you. Obviously, when you do this you should provide functions that always allocate the right number for the user of the code so that there is no magic numbers visible to the end user....

hzhou321 6y ago
> Over allocating is often a very useful strategy. It is not! * If you know exact reasons and exact how much space need (over) allocate, then you should document the reason, and it is no long over allocating. * If you don't know the exact reasons and only know once a while it requires additional space, then you are not solving the problem. You are kicking the can down the road, and it is likely to explode later, possibly with inappropriate timing. * If you know exactly how much the space you need, then the over allocating is just misleading code. Fix Your Code! EDIT: Your comment apparently is for something else. Anyway, the headline needs some counter correction.
- quelsolaar 6y ago
  I'm talking about internal code that is not exposed to the user. There are loads of situations where something will fluctuate in size rapidly, you dont know beforehand to what extent, and allocating memory every-time it changes is very inefficient. In these cases speculatively over allocating is a very good strategy.

sagarm 6y ago

I've written APIs that require extra bytes. The exact requirements can be complex to explain, so to minimize complexity I would just put the maximum over-buffer size in the function docs. As for _why_: knowing that you have a buffer of at least a certain size can allow you to avoid bounds checks, branches, and allocations. For hot loops this can result in a significant performance improvement.

not2b 6y ago

That's a setup for something that used to be a common interview question: how to extend a dynamic string or vector when you need to grow the allocation. If you allocate a fixed amount of excess (say, 5 bytes) when you need to grow the string, then repeatedly appending to your string or vector has quadratic cost. And an early version of Microsoft Foundation Classes (pre-STL, from the 80s) had this bug in the string class.

johnnujler 6y ago

The best way to be safe is to fail loud and clear, and definitely do not surprise your users who only use the api and don’t actually read the source code or how it is implemented.

junon 6y ago

This is somewhat common in branchless parsers. You need a few more bytes at the end of the sequence in order to allow efficient reads to take place. This isn't uncommon, and is why it's pretty important that performance-critical software also RTFM.

FSMaxB 6y ago

My statement: https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d527cd4f1935eec3740d4d95a#commitcomment-44482553 https://github.com/DaveGamble/cJSON/commit/65541b900c740e1d5... At some point I have realised, that just letting cJSON be the horror of a codebase it was before I started maintaining it would have been the best thing to do, but that's what you call hindsight. At least now I know. One reason I burned out was because I felt horrified by how many people are using cJSON and felt a responsibility to make it better and safer for all of them, even though I myself haven't ever been really using it. The combination of this mounting pressure plus the the impossible fight against semantic versioning and memory unsafety gave me the rest. By improving it, but being unable to completely "fix" it, I probably led more people to use it, making the situation even worse than it was before.

sbrki 6y ago

Does anyone know which font is that?

wunderbaba 6y ago

This should be called the "Baker's Dozen" law for engineering.