0

I have a collection of opaque objects and related functions API. Such objects are typically created on the heap, but that involves a non-trivial amount of overhead. And when aggregate together, that adds layers upon layers of extra pointers and indirection.

I would like to be able to compose multiples of those opaque types in structures or as stack objects in order to eliminate the heap memory overhead.

I do know the sizes and alignments of those opaque types, so what would be the optimal way to present that information to the compiler?

I am thinking fixed size byte arrays with explicit alignment. Just wanted to check for a second opinion on whether this is the way to go, and for any potential pitfalls.

Edit: hopefully this clarifies my intent:

struct aggregateHeap {
    OpaqueType1 * op1;
    OpaqueType2 * op2;
    OpaqueType3 * op3;
}; // 3 extra pointers + heap allocation + additional indirection level overhead

struct aggregateStack {
    AlignedBlob(OpaqueType1Size, OpaqueType1Align) op1;
    AlignedBlob(OpaqueType2Size, OpaqueType2Align) op2;
    AlignedBlob(OpaqueType3Size, OpaqueType3Align) op3;
}; // no overhead

void fooHeap() {
  OpaqueType1 * op1 = createOpaqueType1();
  OpaqueType2 * op2 = createOpaqueType2();
  OpaqueType3 * op3 = createOpaqueType3();  
  // use opaque objects with api
} // heap allocation in critical section

void fooStack() {
  AlignedBlob(OpaqueType1Size, OpaqueType1Align) op1;
  AlignedBlob(OpaqueType2Size, OpaqueType2Align) op2;
  AlignedBlob(OpaqueType3Size, OpaqueType3Align) op3;  
  createOpaqueType1(op1);
  createOpaqueType2(op2);
  createOpaqueType3(op3);
  // use opaque objects with api
} // no allocation overhead

void fooAggregateStack() {
  struct aggregateStack agg;
  InitAggregate(&agg);
  // use agg
} // no overhead, much cleaner
7
  • 2
    I think you'll have to be more clear. Structs can't be universally opaque, they have to be transparent to someone, somewhere; it is best to do allocation by the ones who can see the struct, otherwise, your code will have to contain magic numbers (sizes and alignments) and will be subject to logic errors if things change somewhere else, though the compiler won't warn you of them. Not sure what you mean "by layers upon layers of extra pointers". An example would go a long way to clarify. Also, unclear why you're worried about overhead: we shouldn't unless we have performance data.
    – Erik Eidt
    Aug 10, 2021 at 15:43
  • The opaque types come with a set of api functions to which they are transparent. The functions take opaque object pointers as arguments. As I mentioned, I do have the sizes and alignments for each of those, and those will reflect any subsequent internal changes. As for the layers thing - consider the intent to aggregate 3 opaque objects into one structure - the heap approach will give you a struct with 3 opaque pointers to heap objects. So now I once indirect to the struct, then indirect through a struct pointer, that's cpu time overhead plus significant overhead for small opaque objects.
    – dtech
    Aug 10, 2021 at 15:51
  • As for stack vs heap - stack allocation is practically zero cost - it is all pre-allocated, whereas heap allocation isn't, and ends up being orders of magnitude slower for my use case. The API gives me the size and alignment as evaluated by the compiler for the exact purpose to optimize that, allowing me to do the equivalent of "placement new".
    – dtech
    Aug 10, 2021 at 15:56
  • Given the apparent scope of your design, stack allocation doesn't seem advisable. Stack space in most C systems is very constrained. Have you considered pre-allocating space on the heap for this purpose? Aug 10, 2021 at 18:45
  • @RobertHarvey there is no typical or consistent usage pattern for those objects, they are for all intents and purposes the equivalent of what you'd normally put on the stack, rather than something excessively large or pool-friendly. The objects aren't necessarily big, thus the amplification of memory overhead from 64 bit pointers for each of them. It is kind of bad if you use an 8 byte pointer to an 8 byte object, that's 100% memory usage overhead plus additional indirection.
    – dtech
    Aug 10, 2021 at 19:24

1 Answer 1

2

The typical way to create allocatable opaque types is to give up on the opaqueness in the strictest sense, and to declare access to internals as UB. For example, the POSIX pid_t type happens to be a typedef int pid_t in practice.

But here it is important to understand your actual goals.

  • Are you merely concerned about malloc() efficiency?

    If so, create a function that uses an arena allocator. You can't beat the actual stack, but you can get pretty close.

  • Do you want to avoid pointer indirection?

    If so, the type may not have to be totally opaque. In case of C++, you can also declare struct members to be private.

    Also, pointers are not necessarily evil and inefficient. They are most problematic when they make CPU caching impossible, i.e. when you have performance-sensitive code with more data than fits into the CPU caches, and use unpredictable memory access patterns. But even the standard glibc allocator provides good memory locality in most cases, at least for applications that are not very long-running.

  • Are you using plain C and want to avoid pointer indirection and want to keep your types as opaque as possible?

    Strictly speaking, this is not possible. But you can emulate it. Such emulation only makes sense if:

    • you really cannot use C++ (where you'd just declare struct contents private instead);
    • you are writing a dynamically linked library that also needs a clear encapsulation boundary; and
    • you're committed to manually ensuring ABI compatibility with your true struct layout.

    Then, I would recommend to create a struct that has a single char[N] array member of sufficient size, and use appropriate annotations to ensure correct alignment of the struct. You can then reinterpret-cast this struct to your true struct type inside your functions. I think this is technically UB, but safe in practice – everyone does this.

An example of an opaque-ish type is the pthreads mutex type (pthread_mutex_t). In most implementations, it is defined as a struct that contains some metadata + a char array that will be used for internal storage. It can be initialized with the pthread_mutex_init(pthread_mutex_t*, args) function, or assigned directly from the macro PTHREAD_MUTEX_INITIALIZER to get default settings. Of course, the contents of this macro need to know the struct's true internals, but ideally it can just be zero-initialized.

6
  • The intent is to write a code generator for a very small subset of C, it is already implemented as interpreter, but I'd like the option to accelerate it further by generative and compiling C code. Since the goal is to maximize performance, heap allocations and indirections are very undesirable, and I'd prefer for access to follow my specific ABI rather than generating a larger subset of C and having to deal with the quirks of compiler and platform differences in resulting layouts. Internally, all data is passed as as byte pointers, and members are addressed via layout info and pointer arith.
    – dtech
    Aug 10, 2021 at 17:42
  • I also think that having those types as automatic storage blobs may help the compiler do a tad better at optimizing the code, even if it is just all pointer arithmetic and access internally.
    – dtech
    Aug 10, 2021 at 17:44
  • @dtech Well, given those requirements just keeping everything as a char[] makes sense. But since this is a code generator you probably don't have to ensure opaqueness. Given that you're calculating offsets manually (and thus removing any useful type information from the compiler), I wouldn't expect good optimizations though.
    – amon
    Aug 10, 2021 at 18:28
  • I don't have to ensure opaqueness, I just don't care to describe the content of the blob because none of that information is relevant to the usage of the object, all of which is driven by its layout information. This makes it significantly easier to generate portable code, provisioned by the underlying ABI design choices and composition rules. I basically don't have to change anything nor worry about mismatches with compiler/platform specifics. I don't really expect "good optimization", just slightly less bad compared to working with opaque pointers to heap memory and multiple indirections.
    – dtech
    Aug 10, 2021 at 18:41
  • @dtech Fair enough, C is frequently used as a “portable assembly” language. If you need to access data structures with a specific layout there's no way around it. Might not be as portable as you expect though, e.g. if your code performs unaligned memory accesses.
    – amon
    Aug 10, 2021 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.