Inconsistency between the interface of vector bindings and python list & potential wild pointer problems.

[Yikai-Liao]

Following #28 , I'm considering adding inplace argument for other functions. But I find that inplace operation does bring some inconsistency between the interface of vector bindings and python list. Also, this might lead to some wild pointer.

An Experiment

Here is an experiment I conducted:

Theoretical Analysis

Essentially, a python list holds an array of pointers (pointing to the real data), while the std::vector holds an array of the real data. Consider the following code:

notes = [Note(i, 0, 0, 0) for i in range(10)]
note = notes[-1]
notes.insert(0, Note(0, 0, 0, 0))
assert note == Note(9, 0, 0, 0)

For python list, we always expect the note (a reference to the last element of that list) to be Note(9, 0, 0, 0) no matter how we insert or remove elements in the list. Since in such operations, we only move some pointers, and we don't change the position of any real data.

notes = NoteTickList([Note(i, 0, 0, 0) for i in range(10)])
note = notes[-1]
notes.insert(0, Note(0, 0, 0, 0))
assert note == Note(8, 0, 0, 0)

For the vector bindings, e.g. NoteTickList, we do move the real data when insert the new note, while the pointer in note remains the same. Normally (If we don't reach the vector's capacity), the note will still point to the 10th element in notes, which is Note(8, 0, 0, 0). So this is an inconsistency between the bindings and python list.

And if we reach the capacity, vector will automatically copy all the data into a new, larger block of memory and free the original. Then, the note will become a "wild pointer", pointing to an invalid block of memory. If it's unfortunate enough, this will cause your program to trigger a segmentation fault.

In conclusion, even if such inconsistency is acceptable any operations that modify the position of the real data might lead to some potential "wild pointer".

Possible Solution

@Natooz I'm quite concerned about this issue and no perfect solution has been found.

• One possible solution is to disable all operations that change the location of the data, and replace it with a copy, like numpy's append. And as we all know, numpy.append is slow and something that should be avoided.
• Another is to Replace vector<Note> with vector<shared_ptr<Note>>. This makes c++ vectors perform like python lists and introduces a lot of memory fragmentation and overheads.

Both of these schemes introduce a significant overhead, and neither looks elegant or pythonic.

Of course, we could write in the documentation and the README to tell the user not to hold a reference to an event for a long time, but to copy it manually.

But I think there are still a lot of people who don't read these instructions, and then run into the problems I've analyzed.

Improving performance always comes at a price, which can take various forms.

[wrongbad]

For building scores note-by-note, is there any downside to using a python list, and then bulk packing with np.array() at the end? Or just pre-allocating a buffer with number of notes to generate, and set index i++ each step?

[Yikai-Liao]

Sorry for the typo, I meant to say that numba doesn't handle Array of Structure well.

As for your question about whether we can use Python's lists to solve the problem of creating score note by note, it's really a matter of whether the library is AoS or SoA based, and of course both options are possible. symusic inherits from miditoolkit, which is AoS based, and since the data structures are all in c++, the conversion to SoA is very fast.

If you choose SoA-based and use Python's native class to implement AoS, you will face the problem of slow conversion speed.

This is where the tradeoffs need to be weighed based on the usage scenario.

[Yikai-Liao]

This is a schematic of pyvec's memory layout, essentially adding a layer of pointers @wrongbad

Since most of the time we don't adjust the order of the notes we read, I'd say most cases have good memory continuity.

Because ptrs is encapsulated inside pyvec and all pointers in ptrs are required to point to data in buffers, operations such as append force a copy of the object into buffers and release it at the end with other objects in buffers.

Such a data structure also allows us to perform fast slicing, i.e., copying the pointer of the corresponding range and a shared ptr. This is consistent with the complexity of Python list slicing, O(K), where K is the length of the target slice.