Rewriting the cuelist subsystem of Top !

Martin Fouilleul  —  3 weeks, 2 days ago [Edited 0 minutes later]
Hello !

This month I started to rewrite the cuelist subsystem of Top !, using a more low level style and trying to avoid the pitfalls of my first implementation.

That subsystem it responsible for organizing the cues into a cuelist (which is really a tree as group cues can contain other cues), allowing the user to select, insert, delete and move cues into the hierarchy. It also dispatches the gui update requests, recursively computes the timing values through the hierarchy to synchronize everybody, and passes the audio rendering requests to each cue. So it is really the backbone of it all.

It was the first part that I prototyped inside Max/MSP as a bunch of, uh, javascript files, and some C externals. I then translated it when the project moved into its full stand-alone form a while ago, and continued to build around that.
Being somewhat old code, it was also bearing the marks of some habits and preconceptions about "pretty code" that I had not yet completely departed from. Some parts were still unnecessary object-oriented (although I had already calmed down on deep inheritance) with a feeling of wanting to be over-generic, and having more layers of abstraction that were needed. And it was like, heavily relying on dynamic allocation. All that for, let's face it, handling a set of rather simple tasks...

Meanwhile, I think doing more coding, watching the community programming streams and reading other people's code has helped me shift my mind on these things, and I really wanted to try a more pragmatic approach, especially regarding the use of memory.

So here are the kind of changes I'm working on :

  • I set out to replace most (if not all) of the dynamic allocations with an arena based system, much like in Handmade Hero : I malloc a big chunk of memory at the begining, divide it in some memory arenas, and use them to store dynamic data. Each arena is associated with a particular allocator, depending on the purpose of this arena. I implemented the following types of arenas (well, allocators) :

    • A linear allocation arena, where you just append data at the end and never free anything. Braindead simple and useful for all objects whose lifetime spans the whole duration of the application, and for scratch computation buffers whose content can be cleared periodically.
    • A stack arena, where you can push and pop things, it's useful for recursion without recursive function calls (eg. when traversing the cuelist tree).
    • A pool arena, where you can allocate and free fixed-size blocks. Due to this size constraint, it's super fast to allocate/deallocate as it only need to pop or push elements from a "free blocks stack". One other benefit is that the data is mostly contiguous as holes are filled first.
    • A chunk arena, which is a simplified general purpose allocator. It doesn't try to be space efficent and returns blocks on a first-fit basis. I use it for data like user-defined strings (eg. cue names, file names) whose size and lifetime we don't know, and which don't need to be stored in a particular way (eg. be contiguous).
    Using these allocators forced me to think about memory in a much more pragmatic way. One of the surprising (to me at least) insights I draw from all this is that using two linear arenas, one for permanent storage and one for local computation, is surprisingly powerful. In fact most of the time it is really all you need !

  • Initially, each cue type was a class inheriting from a CueNode class with a set of virtual methods like UpdateGui(), AudioRender(), etc. I replaced that with a simple cue_entry struct that packs what is needed for most cue types. It stores a pointer to a cue_object to allow type-specific informations.
    The generic cue_object structure can be extended to suit the need of each cue type, by defining a struct (eg. audiofile_cue, or control_cue) whose first member is a cue_object, and which contains the type specific data (such as a file handle for audio file cues, or a command and target pointer for control cues).
    Cue entries and cue objects are stored separately, each in their own arena. It allows to store entries mostly contiguously with a constant stride, while cue objects can be of varying length. Cue entries, which most of the time contain all the data we need, can thus be stepped through sequentially.

  • In the same spirit, I also isolated the tree structure, which, as the name suggested, was previously kept inside the CueNode. This structure is now described by a collection of cue_node structs, which are stored together in their own pool arena.

  • The dispatch of calls against cue type is made with simple switch statements or function pointers, as is the most convenient for the particular task.

  • The GUI update and the audio callback take advantage of the new memory organization. The parts that need to be done according to the tree structure (such as recomputing the layout of the cuelist when it is edited, or computing the timing value before rendering the audio) can be isolated. The parts that don't really need that ordering can be done sequentially by stepping through the arena of (fixed size) entries. It also opens the way to parallelism as each cue audio output can be rendered separately and out of order.

First thoughts on that new mindset : a breath of fresh air...

Moving things towards this new mindset has proven very refreshing. In particular, having complete control over the memory allocation means you have a way more clear understanding of the way the memory is organized, accessed, and the tradeoffs therein. You can visualize the memory layout and the lifetime of your data much more easily. If something is going wrong, you know were to look.
You have to think about actual expectations, do some back of the enveloppe computation about your memory usage, and think about the way the data is used and moved around before throwing allocations all around, but it gives you a good grasp on the problem you're trying to solve and you don't have to really think about memory management that much after that. You just put the thing in the right place and you're done.

So far I also find that coding with plain old structs and manually handling polymorphism is a pleasure when compared to using classes and virtual methods. It feels a lot more natural and flexible to me. Once again, you can't sweep as much dirt under the rug, as you have to explicitly enumerate types or initialize function pointers. But I find that to quickly turn into a big advantage :

  • The code is more readable because the possibles outcomes are clearly stated.
  • You can always throw in a new version of a function without having to write an entire class, you can even switch function pointers on the fly (although readability might suffer from that), so testing and elaborating from a given starting point is very easy.
  • I find there's less incentive to over-engineer and abstract the data away (maybe because you have less langage features to "hide" things..). As a consequence I find that data structures tend to emerge more naturally from the act of solving the problem and not from preconceptions about the problem.

  • ... but a tough transition from the old code.

    On the other hand, transitioning from the old code is still a work in progress, and I must admit that it's a slow and not always fun process. The big problem is that, starting from a mildly object-oriented and dynamic-allocation-heavy code, the changes can't be really incremental. You have pretty much everything to reconsider and the two styles don't mix very well.
    For instance, using classes with destructors practically forbids the use of linear allocation arenas where you can push things as you go and clear all at once. Also, separating the concerns that were mixed into the CueNode class (maintaining the tree hierarchy, storing common cue data, dispatching type-specific calls) impacted practically all the code, from the gui traversal to the transport logic. You're left with the unpleasing solution of having to break the whole thing down and slowly rebuild it for the most part....

    So there's a lot of dirty work in trying to drag things to the right side, but it's on its way ! I'll keep you updated as I progress through this rewrite. Hopefully, the core subsystem of Top! will emerge from this process in a much more lightweight and robust form than before, and I'll at last be set up for some user-facing changes !

    Thanks for reading,

Log in to comment