SortedSet CPU hit from int size


#1

Hello,

I’m using the sorted set in a vst to store MIDI events every 16th note. The order is not important, just that the CC# and CC_Value happened. I want to be able to store values for two different controllers in a single sorted set (MIDI Channel 1, and MIDI Channel 2). To do this I vectorized the incoming MIDI using code similar to the following:

if (message.getChannel() == channelA)
{
    //vectorize the input
    performerSortedSet.add (message.getControllerValue() + (message.getControllerNumber() * 128));
}
else if (message.getChannel() == channelB)
{
    //vectorize the input
    performerSortedSet.add (message.getControllerValue() + ((message.getControllerNumber() + 128) * 128));
}

The only catch is that I seem to be taking a really big hit for finding the intersection of 2 sets once I add values in ChannelB (10% increase on my macbook). My guess is that its because the numbers are bigger… but a sortedset should be a sparse collection right? So the MAX value wouldn’t determine the collection size, and shouldn’t affect compares like intersection and such right?

Am I missing something? My intersection function looks like this:

int S2MP::numberOfIntersections (const SortedSet<int> &set1, const SortedSet<int> &set2)
{
    int i = 0, j = 0;
    int m = set1.size();
    int n = set2.size();
    
    int intersectionCount = 0;
    
    while (i < m && j < n)
    {
        if (set1.getUnchecked(i) < set2.getUnchecked(j))
        {
            i++;
        }
        else if (set2.getUnchecked(j) < set1.getUnchecked(i))
        {
            j++;
        }
        else /* if set1[i] == set2[j] */
        {
            intersectionCount++;
            i++;
            j++;
        }
    }  
    
    return intersectionCount;
}

Thanks for any thoughts, advice, or help


#2

I did a little more digging and I discovered a bottleneck in the SortedSet.getUnchecked(int) call. It has a Jassert(checkBounds) in it, and it was crushing my CPU. I can totally see the usefulness of this for debugging, but the performance hit was huge for me. I never thought to check the bottle neck at the “getUnchecked(int)” function, as I was trying to use that to speed up my intersection function. Maybe there could be a way to enable or disable array Jassert protection in debugging? That way we could see performance improvements, and also debug array bounds issues.


#3

You could set JUCE_DEBUG=0. But TBH I use that function in all kinds of performance-critical code and have never noticed it being slow, which kind of suggests that’s your algorithm needs improving rather than blaming the assertion… E.g. you could double the speed of your code (in release mode, too) by just storing set1.getUnchecked(i) and set2.getUnchecked(j) in local variables rather than duplicating the same calls. And you could also use begin()/end() iteration rather than indexes to do the whole thing via raw pointers, which is probably faster anyway.


#4

Thanks for the tips. I didn’t notice that I was calling the getUnchecked() twice. I saw that the C++ std::set_intersection function used pointers as well, so I’ll try and model the intersection after that.

As to the algorithm, its based off of this similarity matching algorithm called S2MP (http://hal.inria.fr/docs/00/32/44/88/PDF/CRPITV87Saneifar.pdf). Its a cool way to do a concatantive synth thing, but it does a lot of nested looping (and the intersection is the inner most loop).

btw, whats the best way to do sortedSet operations like union, difference, and intersection? Are there JUCE classes I should be using, or are they meant to work with ?


#5

Nice! I just switched my iterator code to use begin()/end() like you suggested, and it works perfect in debug now. Ableton now shows 2-3% cpu vs crazy meaningless cpu usage like 520%+

For anyone interested in the intersection code for the sorted set, I’ve posted it here and its based off of http://www.cplusplus.com/reference/algorithm/set_intersection/

[code]int S2MP::numberOfIntersections (const SortedSet &set1, const SortedSet &set2)
{
int* first1 = set1.begin();
int* first2 = set2.begin();

int* last1 = set1.end();
int* last2 = set2.end();

int intersectionCount = 0;

while (first1 != last1 && first2 != last2)
{
    if (*first1 < *first2) ++first1;
    else if (*first2 < *first1) ++first2;
    else /* set1[i] == set2[j] */
    {
        ++intersectionCount;
        ++first1;
        ++first2;
    }
}  

return intersectionCount;    

}[/code]