Slashdot Mirror
C Coding Tip - Self-Manage Memory Alllocation
An anonymous reader inputs: "The C programming language defines two standard memory management functions: malloc() and free(). C programmers frequently use those functions to allocate buffers at run time to pass data between functions. In many situations, however, you cannot predetermine the actual sizes required for the buffers, which may cause several fundamental problems for constructing complex C programs. This article advocates a self-managing, abstract data buffer. It outlines a pseudo-C implementation of the abstract buffer and details the advantages of adopting this mechanism."
Of course, there are also hard real-time garbage collectors (ie Cheng's), though I don't think you'll find them in general-purpose production compilers. However, you will find good garbage collectors in a number of real production compilers (say, in mlton). It's definitely worth benchmarking.
The article basically proposes a very bad implementation of Vstr, most of the advise was extremly simplified at best but more likely just uninformed: an "efficient" abstract buffer that mixes shorts and pointers -- words almost fail me, how to solve the problem of "what do you do with the data when it's all in the buffer" -- "let's just copy it back out again (hey whats a couple of extra copies between friends). Representing in memory object sizes with "long int" *sigh*.
If you are interested in the article, go read this explanation of why you want it for security and this explanation of why you want it for speed .
Vstr is LGPL, has actual benchmark data behind the block sizes it picks, has an extensive test suite ... and has documentation for the many functions that come with the library (including a fully compliant printf like function). Of course, I don't have a PhD ... but after reading this, you might well count that as a plus too
ustr: Managed string API with ave. 44% overhead over strdup(), for 0-20B
Often C++ code is faster than the equivalent C code since the compiler has more information to work with and the programmer can make use of more effective techniques like templates.
Forget C++! High-level modern multi-paradigm languages like Common Lisp and OCaml, which can do most things C++ can do and a lot of things it can't, often produce code as fast as the average C implementation of any given algorithm, despite their relying heavily on GC. And while it's generally possible to tweak the C version to be faster, bear in mind that the C already takes longer to write and debug, even without allowing for the time-consuming profile/tweak/rebuild cycle that real optimisation requires.
Personally I've already relegated C to the position that assembly used to hold - I drop into C to write very tight loops, to perform low-level bit twiddling, and to interface with other languages. I wouldn't really consider using it to write an entire application, and the time I save by not having to manage resources myself is one of the major factors that rule it out.
Embedded systems do this, they have a pool of Buffers and a BufferManager that allows you to do effectively your own memory mangement (and in some cases, static memory management). malloc() and free() are usually really slow, so if you can save 99% of those calls by reusing memory blocks, you can really speed up your programs.
The biggest trick the devil pulled was letting lawyers become politicians so they can write the laws.
I said facts, not theories. Yes, I know all about cache and his friend random access. Maybe you'll take a noticable cache hit when moving between nodes ... and yes, certainly doing memcpy() over a single large block X will be faster than doing it X/20 times for 20 byte nodes (20 was the figure given in the IBM "research" article). But that doesn't take into account the time taken to call realloc() each time to expand the large block ... or the amount of space wasted if you have a large amount of data followed by mostly small amounts of data ... or the sharing that is possible in a node based system (thus almost eliminating the cost of copying).
And I did provide the simple benchmarks (which showed that with sane node sizes the vector approach is better than realloc() + memcpy()), and code for somewhat more complication cases that try to model simple network IO applications (which show the single block of memory is only competitive when you use more memory and add complication to the algorithum to reduce copying ... or use lots more memory).
But feel free to prove me wrong, I'd certainly study anything you came up with. And yes, I'm taking the csv code into account ... on normal input the node based code was within 50% IIRC, and on "difficult" code it was over 100% faster (again IIRC) ... and your code was a lot more hand optomized.
ustr: Managed string API with ave. 44% overhead over strdup(), for 0-20B
So in the presence of exceptions, you won't leak memory on the heap. But you will leak mutexes, file handles, etc. You need another idiom to handle those cases.
.NET world, C# introduced synchronization blocks to handle the leaking mutex problem. But it is a pain in Managed C++ and VB.NET.
In the
File/mutex/whatever leakage in the presence of exceptions? Two words:
unwind-protect
--WH--