March 23, 2004

Things to not do in code #18

I oughta collect these all up, but...

Never, ever do in two allocations what you can do in one. For example:

  struct foo {
struct bar *thing;
int this;
int that;
};

struct bar {
int data[128];
}

See the problem there? What happens is that you allocate a foo, then allocate a bar and put a pointer to it in the foo. Which makes sense if bar is of variable-length, but... in this case it isn't. Even worse is the case where bar has a pointer to a glob of memory which is of fixed-size.

Why does this suck?

First, it means you've got multiple allocations. Two or three, instead of one. That messes up your free list more.

Next, more allocations means more chance of failure. If you've got one big damn structure then allocate it as one big structure. Breaking it in pieces that are all required just means you've more chances to screw up the error handling.

Third, you waste memory. That thing pointer in the foo struct's completely irrelevant. Sure, it's only 4 or 8 bytes, but that's about a third of the structure in our case. (Which isn't even that degenerate as these things go) Adds up.

Fourth, you waste time. Getting to bar requires an extra pointer indirection action. A lot of time? No. But some, and difficult for the compiler and CPU to predict. You've a good chance of adding a half dozen cycles to access elements of bar because of it.

Fifth, you waste time more. Different allocations have a good chance of being in different areas of memory, especially if they're of significantly different sizes. (Many memory allocators have separate free lists for different sizes of memory, so a 32 byte allocation comes from a different pool than a 1024 byte one) That means you lose any locality of reference and odds are have to fault at least two pages from main memory into L2 cache, and guaranteed two separate cache lines into L1. The L1 fault may not be any different, though, depending on how much of each structure you access, so you may pay for the same number of L1 faults, but... You're also using more L1 cache because of the extra pointer.

Yeah, yeah, there's always that 'Well, it's conceptually clean' argument, or the "Separate things should be separate!" one. If that's actually true, great. Separate them. If they aren't, then don't, dammit! If it's a big single thing, make it a big one. Want to make it easy for yourself by breaking it up? Fine. In that case, the declaration above should be:

  struct foo {
struct bar thing;
int this;
int that;
};

struct bar {
int data[128];
}

See the difference? (Ignore the squawks from the compiler about forward declarations) foo contains bar, rather than points to bar. If that's how the structure's modelled, then that's how it should be declared. You still get that encapsulation you want, without the costs.

If you're tempted to launch the "Well, what if I need to refactor it?" retort, don't. If you were worried about that, then allocation and access would already be factored out into separate routines so it wouldn't matter, and trust me, the compiler will pitch a major fit if you miss changing dereference punctuation to structure accessing punctuation if you've not done that.

Posted by Dan at March 23, 2004 11:58 AM | TrackBack (0)
Comments


This choice (inclusion versus pointer) is actually pretty similiar to SQL's "should I put this column into separate table, or add it to the existing table". The answer is usually "don't fork the new table, joins are slow".

Sure, most of the times, earlier or later, some *other* relationship (table) would demand access to this 'new' table.

Well at *that* point it will be OK to fork a new table and mess with joins ('start using pointers').

However, I think that only a fool will fork that new table 'in advance', 'just in case'.

Posted by: PaulT at March 26, 2004 04:58 PM

Never ever? Never ever ever? Even when sizeof(struct foo) is 12 (without bar inlined) and sizeof(struct bar) is, say, 64 kilobytes?

Posted by: jhi at March 31, 2004 04:22 PM

Never, ever, ever.... ever. And not even then either. :)

If the two structs are logically one struct that won't be split and can't be independent then they should be allocated as a single atomic unit. Yeah, there are a few odd edge cases that make it worth splitting them for real, but unless you've a significantly fast-path allocator for structs of just the right size of things split up, there's just no reason.

That's not to say that there aren't times when separate structs with pointer linkage are the right thing to do--often it is, and sometimes the trick is to figure out when you're linking and when you're just conceptually segregating a single entity.

Posted by: Dan at March 31, 2004 04:58 PM

There I was, wondering what the hell all those structures reminded me of, and about halfway through, it hit me - you're basically talking about the sockaddr / sockaddr_in / sockaddr_un / sockaddr_in6 / sockaddr_of_the_week structure separation, though in your case the two structures seem to be a bit more closely related. The sockaddr family also shows a generic solution, when the structures are not necessarily known at compile time or even at design time - place a char array placeholder at the end of the generic structure and pass a length parameter to all accessor routines. And, of course, allocate your sockaddr_of_the_week structure in one piece :)

Posted by: Peter Pentchev at April 21, 2004 05:17 PM