17 ms·
Why does calloc exist?
- wyldfire 10y ago> So basically, calloc exists because it lets the memory allocator and kernel engage in a sneaky conspiracy to make your code faster and use less memory. You should let it! Don't use malloc+memset! On the flip side, if your critical metric is latency then these tricks of calloc's and the OS's are exactly what you try to avoid. memset() the buffer, and if you have the privileges you should mlock() it to prevent it from being paged out. Of course, this all presumes that it's not an ephemeral buffer to begin with. Best to change your design to leverage a long-lived resource if possible.
- valarauca1 10y agoBest to change your design to leverage a long-lived resource if possible. On the flip side, if your critical metric is latency then these tricks [...] are exactly what you try to avoid If you keep the buffer alive as long as possible with a slab allocator, or just smart/good memory management strategy. How you acquire the buffer will ultimately be trivial, likely dwarfed your other startup tasks (reading config, opening sockets, etc.)
- rcfox 10y agoI think he was referring to the part where a calloc'd memory page will be zeroed the first time it's used, rather than all at once at the beginning. In a real-time system, the start-up time matters less than having predictable response times.
- valarauca1 10y agoIn a realtime system you can't use virtual memory because the access times are unpredictable.
- wyldfire 10y agoI specifically avoided that word because it triggers particular deadlines that people have in mind. If my application requires no more than X ms latency I don't care to handwring over realtime vs soft realtime vs whatever, but it's still critical to fit in the budget. But indeed you can get reliable low-latency products to work on linux, with virtual memory. But like I said pinning is a great way to keep those peaks down.
- valarauca1 10y agoThe division you are looking for is Hard Realtime: Embedded system, no virtual memory/OS. Or special OS provisions to let them run. Soft Realtime: Responsive. In the case you are aiming for the second. There are several million things that'll net greater performance. We're talking about saving a matter of nano-seconds in C/C++. How you load your config will have more effect then this. If you want to save $1,000,000 rolling pennies a start. But there are likely way bigger savings elsewhere, worth way more time, and less effort.
- karmakaze 10y agoI didn't think how it's achieved matters to the classification which is by the consequence of missing a deadline according to good ol' Wikipedia: Hard – missing a deadline is a total system failure. Firm – infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline. Soft – the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service
- valarauca1 10y agoYour difference between soft/firm is an arbitrary decision made by a manager, not really a hard/fast If I can't meet this deadline my system is a total technical failure. You've created a false dichotomy.
- gkfasdfasdf 10y agoAnd if you really want to squeeze the last bit of performance out you could not memset / init the memory at all, and make sure you only read the parts your app has written.
- bluefox 10y agoThat's a nice alternative history fiction. Here's an early implementation: https://github.com/dspinellis/unix-history-repo/blob/Research-V7/usr/src/libc/gen/calloc.c https://github.com/dspinellis/unix-history-repo/blob/Researc...
- colanderman 10y agoIt's a good explanation of why calloc still exists and is useful. Otherwise it would have been dropped from the standard like cfree was.
- viraptor 10y agoI think there's a big difference between "why does ... exist" and "why does ... still exist". calloc() may be useful today for reasons completely different from why it existed in the first place. And the difference #2 is just an implementation-specific optimisation. There's nothing in the standard that forces calloc to use lazy allocation / virtual memory. Actually, it may be implemented on platforms which can't provide this.
- greglindahl 10y agoThank you for bringing up the implementation-specific nature of #2! If the author is running Linux, then perhaps they've never checked out overcommit vs. not overcommit.
- mikeash 10y agoYou're likely to still see a performance improvement without overcommit. The OS will try to zero free pages in the background, so there's a good chance that it'll have pre-zeroed pages to hand you when you ask for them, rather than making you wait for them to be zeroed on demand. Of course, there are plenty of systems where this doesn't happen, or there are no pages in the first place, or there's no kernel zeroing stuff for you.
- Someone 10y ago
- Animats 10y agoThe real reason "calloc" exists was that it was really easy to hit 16-bit overflow back in the PDP-11 days.
- raphaelj 10y agoThank you for this answer. The answers from OP were not convincing me.
- raphaelj 10y agoThank you for this answer. The answers from OP were not convincing me.
- LukeShu 10y agoHistorically, not quite true. No version of Research UNIX V1 through V7, nor any of BSD 1, 2, 3, 4, or 4.4 did overflow checking. They all just did `m * n` or `m *= n`.
- jcranmer 10y agoIf you look through the history of CVEs, you'll find that pretty much every implementation of calloc or a calloc-like function starts with m * n and ends up only changing after someone points out the security flaw.
- notacoward 10y agoI always thought it was because of padding. An array of M structures each N bytes long could require more than M*N bytes (certainly has on some architectures I've worked with). But I guess that's not it after all.
- to3m 10y agocalloc doesn't know what it's allocating for, so it has to hand out m * n. (Despite the syntax, the same goes for operator new in C++! Placement vector new in particular is a trap.)
- tedunangst 10y agoPadding is included in sizeof.
- mikeash 10y agoC accounts for padding in the size of the individual type. By the time you do sizeof, it's already rounded up to where you can just do M*N. For example: struct S { long a; char b; }; On my computer (64-bit Mac), sizeof(struct S) is 16, due to 7 bytes of padding after b. Since the compiler handles the padding, that means calloc doesn't have to.
- xxpor 10y agoWhich can lead to sadness if you're not careful with #pragma pack and the like.
- notacoward 10y agoToday's compilers. How about the compilers when calloc was first defined? As I said, I've worked on compilers that behaved differently, either always or according to various options. The computing universe has actually become less diverse in some ways than it used to be, so we should be careful of drawing conclusions about old interfaces based on today's monoculture. Is it really impossible for people here to imagine that some of the dozens of platforms that had their own compilers and C libraries chose to do the rounding up in the latter? It would actually be a pretty reasonable choice, for different microarchitectures capable of running the same instruction set and binaries but with different cache subsystems. That way you could make the decision at run time instead of compile time. Many of the early RISC machines did even weirder tricks than that to wring out the last bit of performance on multiple generations without having to recompile.
- ben_bai 10y ago> Plus, if we wanted to, we could certainly write our own wrapper for malloc that took two arguments and multiplied them together with overflow checking. And in fact if we want an overflow-safe version of realloc, or if we don't want the memory to be zero-initialized, then... we still have to do that. Like reallocarray(3) does? buf = malloc(x * y); // becomes buf = reallocarray(NULL, x, y); newbuf = realloc(buf, (x * y)); // becomes newbuf = reallocarray(buf, x, y);
- syntheticnature 10y agoreallocarray(3) looks nifty, but until it's available on a wider, ideally more standard-driven basis than just OpenBSD and FreeBSD, it's likely to not see wide uptake.
- brynet 10y agoIt's already gaining adoption outside of the BSDs. OS X/iOS seem to have it as part of their libmalloc. Android Bionic libc has it as part of the code they sync from upstream OpenBSD. Many open source projects include their own, or simply bundle the OpenBSD implementation: * mandoc * flex * unbound and nsd * tor * tmux * libbsd * libressl * xorg-xserver * ... The list only continues to grow, several more examples to be found on GitHub.
- klodolph 10y agoDarwin (macOS / iOS) is often counted as "one of the BSDs", just a fairly weird one. Big chunks of the standard library are copied from FreeBSD with changes to work on top of Mach.
- achivetta 10y agoThere's code for it in Darwin's libmalloc, but it's not exposed as API. reallocarray() has some difficulties as an interface, mostly inherited from realloc(). I'm a bigger fan of reallocarr(), but that's NetBSD only. We (the operating systems community) need to find a consensus here, but I'm not convinced that reallocarray() is that consensus yet.
- rcthompson 10y agoI you calloc some memory and then the first thing you do is write to it, can the compiler optimize away the initial write of zeros since they will just be overwritten?
- radarsat1 10y agoI would imagine this might work in cases where the compiler can prove that all addresses are written, but probably this is a limited number of cases. Likely it would do so simply by noticing two successive writes to the same location, instead of doing anything special related to calloc.
- Serplat 10y agoFor smaller memory allocations that don't go directly to the OS, I suppose it's theoretically possible (though I'm not sure any compilers do it). For the larger allocations that the author mentions that go directly to the OS to fulfill, however, the compiler wouldn't be able to optimize this away. In that case, the zero'ing occurs in the kernel, which is something that the compiler has no control over. The zero'ing is done significantly for security reasons anyway. If a program could somehow disable that feature and get leftover memory from the kernel it could very easily contain password, secret keys, and other important bits of data that you wouldn't want random programs on your computer to have access to.
- deleted 10y ago[deleted]
- caf 10y agoPossibly, for small allocations: a possible way this can happen is a small-value `calloc()` inlined as a `malloc()` / store zeroes pair, and then the "store zeroes" part of that discarded by a later optimisation pass as a dead store. On modern server/desktop/mobile CPUs, this won't make much difference anyway because the second write to the same location is essentially 'free' due to the store buffer. And of course if you're calling calloc() in a tight loop, then the zeroing is the least of your performance concerns!
- DannyBee 10y ago
- jedisct1 10y agoGood operating systems also provide `reallocarray()`.
- deleted 10y ago[deleted]
- astrobe_ 10y agoIt's in the standard library, not in the operating system.
- binarycrusader 10y agoThe standard library is usually delivered as part of the operating system on *nix-like platforms.
- masklinn 10y agoIn fact the standard library is usually part of the operating system in the sense that it's the interface to the OS, on both nix-line and non-nix like systems. Linux is the exception (in that raw syscalls are officially supported) not the rule.
- binarycrusader 10y agoYes, exactly. This is especially true on Darwin and Solaris.
- deleted 10y ago[deleted]
- astrobe_ 10y agoMaking statements as inaccurate as possible without being wrong is a fun game, I guess. My turn: A file explorer is part of the OS because it is installed by default on Windows. A good OS provides a graphical file browser.
- smegel 10y ago> But calloc lives inside the memory allocator, so it knows whether the memory it's returning is fresh from the operating system, and if it is then it skips calling memset. And this is why calloc has to be built into the standard library, and you can't fake it yourself. Err...mmap(2)?
- theseoafs 10y agoYou can't fake it yourself from within the C stdlib is what the author means.
- _RPM 10y agobuf = calloc(huge, huge); if (errno) perror("calloc failed"); printf("calloc(huge, huge) returned: %p\n", buf); free(buf); This has a flaw. errno doesn't magically get reset to zero. You should check the return value of calloc, then use errno. Checking if(errno) is not the right way to determine if there was an error.
- avar 10y agoIts [errno's] value is significant only when the return value of the call indicated an error (i.e., -1 from most calls; -1 or NULL from most library functions); a function that succeeds is allowed to change errno.
- imron 10y agoNote the difference between "is allowed" vs "must". If you write a program that relies on this behaviour you're going to have a hard to track down bug at some point.
- takeda 10y agoThat's even stronger case for not relying on errno to catch errors. The code should be something like this: buf = calloc(huge, huge); if (!buf) perror("calloc failed"); printf("calloc(huge, huge) returned: %p\n", buf); free(buf);
- MaulingMonkey 10y agoIt's harder to forget to multiply by sizeof(T) when calloc-ing as well.
- topkekz 10y agoyou can do sizeof(T[n]) instead of sizeof(T) * n
- wfunction 10y agoNo, the 2 GB array should still take a quota of 2 GB. It just wouldn't take 2 GB's worth of time to initialize. The overcommit "feature" in Linux is a bug that crashes C programs in places that violate the language's guarantees (such as when a write occurs to a location in memory that was allocated correctly).
- jblow 10y agoSorry, but this is just goofy and bad. If you depend on copy-on-write functionality, then you need to use an API that is specced to guarantee copy-on-write functionality. If that means you use an #ifdef per platform and do OS-specific stuff, then that is what you do. Anything else is amateur hour. If copy-on-write is a desirable feature, then as the API creator, your job is to expose this functionality in the clearest and simplest way possible, not to hack it in obscurely via the implementation details of some random routine. (And then surprise people who didn't expect copy-on-write with the associated performance penalties.) This is why we can't have nice things.
- kccqzy 10y agoI think the author's point is opportunistic optimization. He didn't ask us to rely on this behavior.
- jblow 10y agoIf you don't know whether or not you are really getting an optimization, then how much do you really care? If you really care, then you actually profile your system and see what takes how much time, under which circumstances. The results of such a profile are almost always surprising. I guess this is a basic cultural difference -- almost nobody in the HN crowd really cares whether their software runs quickly; there is just a bunch of lip service and wanting-to-feel-warm-fuzzies, with very little actual work. In video games (for example) we need to hit the frame deadline or else there is a very clear and drastic loss in quality. This makes this kind of issue a lot more real to us. If you look at the kinds of things we do to make sure we run quickly ... they are of a wholly different character than "guess that calloc is going to do copy-on-write maybe."
- kllrnohj 10y agoAt the same time why would you ever opt to malloc & memset instead of calloc? calloc might have clever optimizations, whereas malloc + memset won't. Intentionally choosing something slower, buggier, and that requires more work on your part is moronic.
- dimman 10y agoThere are some unfortunate statements in there (if taken out of context) that requires you to read the whole thing for it to make sense. Like "...but most of the array is still zeros, so it isn't actually taking up any memory..." which is a bit ambigious if not read in the complete context, then it makes sense.
- duaneb 10y agoThis is a great example of why _alloc is an abstraction over virtual memory. What this doesn't express is that dealing with page allocation directly can be quite annoying to get correct cross platform. You generally don't want to do that unless a) you're optimizing past the "knuth level" and know you need to for performance (e.g. mapping files to memory), b) you're writing something where you run dynamic code (JIT or dynamic recompilation) or c) you're writing your own allocator and/or using page faults to get some functionality, ala Go's stop-the-world hack. Basically, don't bypass _alloc unless you have a reason.
- AceJohnny2 10y ago> And at least we aren't trashing the cache hierarchy up front – if we delay the zero'ing until we were going to write to the pages anyway, then that means both writes happen at the same time, so we only have to pay one set of TLB / L2 cache / etc. misses. Ooh, nice one. My first impression was that calloc was just lazy-allocating, which is fine in most cases but when you want precise control over timing, maybe you want to be sure that memory is zero'd at allocating time rather than pay the cost unexpectedly at use time. But the cache-awareness makes that a moot point. You'd be paying double cache-eviction costs if you were clearing that memory up front: once at clearing time, and once at actual-writing time. This implementation of calloc avoids that.
- Manishearth 10y agoI've always been surprised that memset is usually just a nonmagical for loop. I used to expect that the OS does things to magically make it faster (running lazily, etc).
- caf 10y agoCPUs are pretty great at running nonmagical for loops, so you'd have be zeroing a pretty giant block of memory before it made sense to get the OS involved at all.
- Manishearth 10y agoOf course :) But the OS could get involved for larger blocks of memory. Also, I wonder if zeroing large chunks of memory would be faster to do in kernel space using real addresses. You can avoid the multiple real memory lookups involved in a single virtual write. (Of course, we already avoid those often, but it could be useful to avoid entirely. Not sure what the tradeoffs are here)
- caf 10y agoPaging is still enabled in kernel mode, the kernel uses virtual addresses. (The kernel's linear mapping of physical memory can take advantage of huge pages though, which means that there might be one or two less levels of page tables involved with those addresses). TLB misses aren't significant if you're bulk-writing to a block of memory anyway, you'll max out the bandwidth of the memory without that being an issue.
- adrianN 10y agoFor linear access patterns the TLB does its job perfectly. The overhead is negligible.
- chei0iaV 10y agoWhich implementations use a nonmagical for loop? glibc's is all in assembly full of SIMD instructions, which seem very much magical... https://sourceware.org/git/?p=glibc.git;a=tree;f=sysdeps/x86_64;hb=HEAD https://sourceware.org/git/?p=glibc.git;a=tree;f=sysdeps/x86... http://stackoverflow.com/questions/8858778/why-are-complicated-memcpy-memset-superior http://stackoverflow.com/questions/8858778/why-are-complicat...
- edblarney 10y agoWhy do so many people disagree on something that should be nearly empirical?
- nicolast 10y agoAnd then there's of course when calloc returns non-zeroed memory once in a while, which causes... 'interesting' bugs. https://bugzilla.redhat.com/show_bug.cgi?id=1293976 https://bugzilla.redhat.com/show_bug.cgi?id=1293976 http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-5229 http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-5229
- Const-me 10y agoLet’s see what happens after the allocation. With malloc + memset, the OS will likely allocate that memory in huge pages, on PC that would be 2-4MB / page depending on the architecture, https://en.wikipedia.org/wiki/Page_(computer_memory)#Huge_pages https://en.wikipedia.org/wiki/Page_(computer_memory)#Huge_pa... If I calloc then write, the OS can’t give me huge pages because of that copy on write thing. Instead, the OS will gradually give me the memory in tiny 4kb pages. For large buffers you should expect TLB cache misses, therefore slowing down all operations with that memory.
- amluto 10y agoI don't think your average kerbel can tell the difference between malloc+memset and calloc.
- kr7 10y agoA quick test with strace on my machine shows that callocing and mallocing a 2GB buffer results in the exact same mmap system call for both. Neither use huge pages.
- mikeash 10y agoThere's no reason the OS can't use huge pages for a calloc. In fact, "give me some zeroed memory" tends to be the only interface exposed by the kernel, since security requires zeroing memory before handing it out to userspace anyway.
- Const-me 10y agoThis article _creates_ a reason why the OS might not be able to use huge pages for a calloc. If substantial count of people will read this article, believe what’s written, and [re]design their software under the wrong assumption calloc returns sparse copy-on-write memory buffer at no performance cost — the OSes will no longer be able to use huge pages for a calloc. Because doing that would dramatically increase physical memory usage for such software.
- IgorPartola 10y agoI don't get it. The two behaviors are completely orthogonal. Why can't I have a malloc() that does lazy copy-on-write for large arrays and why can't I have an error checking malloc() and why can't I have a calloc() that allocates the memory up front and doesn't zero it out? I get the "it's historic" argument, but this seems like a silly distinction. Sounds like what you want to do practically is basically just make your malloc() wrap a calloc() with size 1, and stop explicitly memset()ing. Or just introduce your own functions: moarmem(n) // malloc(n) moarmemslower(n) // p = malloc(n); memset(p, 0); moarmemfaster(n) // calloc(n, 1) evenmoarmem(p, n); // realloc() fuggetaboutit(p) // free()
- kr7 10y ago> Why can't I have a malloc() that does lazy copy-on-write for large array malloc will generally do lazy copy-on-write above a certain limit; it was 128kb for glibc last time I checked. > why can't I have an error checking malloc() reallocarray is becoming the de-facto standard for that. > why can't I have a calloc() that allocates the memory up front and doesn't zero it out? Er, malloc?
- masklinn 10y ago> Why can't I have a malloc() that does lazy copy-on-write for large arrays reallocarray(3) (though fundamentally that's what malloc does as well, it just doesn't do overflow checking) > why can't I have an error checking malloc() reallocarray(3) (because malloc doesn't get the information, it gets a single size rather than a count and a per-object size) > why can't I have a calloc() that allocates the memory up front and doesn't zero it out? reallocarray(3) > Sounds like what you want to do practically is basically just make your malloc() wrap a calloc() with size 1, and stop explicitly memset()ing. If you're going to memset(0) it there's no reason to use malloc() ever, but it's very common to malloc() then fill the allocation directly, in which case the memsetting is a redundant cost.
- developer2 10y agoAs a non-moderator, can you please stfu article author with your political piece prefixing the article. If your reaction to being linked to from HN is to push your own political agenda, you are no better - and possibly worse - than the moderators. Using your 15 minutes of fame to edit your article with a preface containing a dozen links unrelated to the article you were linked to for is disgusting. It's not appreciated to click through to an article about calloc, only to find unwarranted political garbage that nobody cares about. I flagged the article for this. How ironic that were enough people do this, it would be taken as "HN censorship" rather than "normal users saying they are displeased with the manipulative editing of the submitted link". Quoted for history: >> Welcome Hacker News readers! Before we dive into the neat memory management esoterica, I want to briefly note that as engineers we have an ethical obligation in our work to consider the "safety, health, and welfare of the public", because if we don't, terrible things happen. This is a challenging responsibility that requires we all stay thoughtful and informed – but that's difficult if popular technical news aggregators choose to censor links and discussions about the societal implications of technology. I sympathize with their moderation challenges, but this idea of creating a politics-free safe space is the cowards' way out, quite literally choosing the "absence of tension" over "the presence of justice". I hope the HN moderators find a way to step up to the responsibility their position entails; in the mean time, you might consider also subscribing to to The Recompiler and Model View Culture, and checking out Safety Pin Box, techsolidarity.org, or Fund Club. Anyway, thanks for listening! We now return to our regularly scheduled calloc-related programming, and I hope you enjoy my essay. And if you like this, you might also enjoy Cory Benfield's related post.
- MichaelBurge 10y agoI suppose another alternative would be for memset() to check if the page is already mapped to the zero page, and to do nothing if it is. There are some bitset-related data structures that should make that pretty efficient.
- drfuchs 10y agoOriginally, calloc was the function Unix programmers were expected to use by default, since it avoids any sort of intermittent bugs due to your forgetting to initialize some field in the data structure you're allocating. But clearing the memory to all zeros took precious time, so if you were an advanced programmer, and knew for a fact that you were going to fill it all in yourself, you could optimize by calling malloc.
- angusp 10y ago> I mean, let's be honest: if we really cared about security we wouldn't be writing in C. How so? C is low level, so to be secure you must be fully aware of the behaviours and side effects of what you're doing. In another, perhaps higher level language, sure, there may be less of these gotchas but to be properly secure you need a similar amount of knowledge about background behaviour.
- kamouth 10y ago"(I mean, let's be honest: if we really cared about security we wouldn't be writing in C.) " Why so ?
- BugsBunnySan 10y agoShould be the other way around, shouldn't it: "Only if you really care about security should you be allowed to write in C" :) (i.e., don't use a professional-grade band-saw, if you're not a professional)
- Waterluvian 10y agoNot sure how I feel about, "oh everyone's looking this way! Let me get political"
- tdeck 10y agoReally felt like a bait and switch to click that link and get an angry rant.
- ericfrederich 10y agoSomebody needs to go update all the StackOverflow answers saying that malloc is faster. According to this, calloc seem to always be faster with several other benefits as well.
- bcpermafrost 10y agoIt is not as you say. The article suggests that Malloc + Memset is slower than Calloc. Malloc will be faster depending on your use case. If your plan is to eventually call memset. Then just use Calloc, otherwise malloc will be faster all the time.
- Twirrim 10y agon00b question: Why would you not memset? I would assume you'd want to start with all zeroed memory in almost all cases.