2
\$\begingroup\$

I'm within an audio application that sends variable-length buffers to my DLL, which will process at higher speed (48000 samples per sec, but can also be higher).

Here's the code I've written:

while (remainingSamples > 0) {
    int blockSize = remainingSamples;
    if (blockSize > PLUG_MAX_PROCESS_BLOCK) {
        // PLUG_MAX_PROCESS_BLOCK = 256
        blockSize = PLUG_MAX_PROCESS_BLOCK;
    }

    // voices
    for (int voiceIndex = 0; voiceIndex < 16; voiceIndex++) {
        for (int envelopeIndex = 0; envelopeIndex < 10; envelopeIndex++) {
            Envelope &envelope = *pEnvelope[envelopeIndex];
            EnvelopeVoiceData &envelopeVoiceData = envelope.mEnvelopeVoicesData[voiceIndex];

            // skip disabled envelopes (in the case of test, all are running)
            if (!envelope.mIsEnabled) { continue; }

            // envelope voice's local copy
            double blockStep = envelopeVoiceData.mBlockStep;
            double blockStartAmp = envelopeVoiceData.mBlockStartAmp;
            double blockDeltaAmp = envelopeVoiceData.mBlockDeltaAmp;
            double values[PLUG_MAX_PROCESS_BLOCK];

            // envelope local copy
            bool isBipolar = envelope.mIsBipolar;
            double amount = envelope.mAmount;
            double rate = envelope.mRate;

            // precalc values
            double bp0 = ((1 + isBipolar) * 0.5) * amount;
            double bp1 = ((1 - isBipolar) * 0.5) * amount;

            // samples
            for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
                if (blockStep >= gBlockSize) {
                    // here I'll update blockStartAmp, blockDeltaAmp and fmod blockStep, every 100 samples. but I'm ignoring this part right now
                }

                // update output value
                double value = blockStartAmp + (blockStep * blockDeltaAmp);
                values[sampleIndex] = (bp0 * value + bp1);

                // next phase
                blockStep += rate;
            }

            // restore back values from local copy
            envelopeVoiceData.mBlockStep = blockStep;
            envelopeVoiceData.mBlockStartAmp = blockStartAmp;
            envelopeVoiceData.mBlockDeltaAmp = blockDeltaAmp;

            // mValue is a mValue[PLUG_VOICES_BUFFER_SIZE][PLUG_MAX_PROCESS_BLOCK];
            std::memcpy(envelope.mValue[voiceIndex], values, PLUG_MAX_PROCESS_BLOCK);
        }
    }

    remainingSamples -= blockSize;
}

But it keep still 3-4% of CPU iterating 16 voices, 10 envelopes and 256 samples. Is there any way to speed up this task? Vectorizing maybe? I'm not really able to do it.

Any tips?

Here's an extract of Envelope.h header:

#ifndef ENVELOPE_H
#define ENVELOPE_H

const unsigned int gBlockSize = 100;

struct EnvelopeVoiceData {
    double mBlockStep;
    double mBlockStepOffset;
    double mBlockStartAmp;
    double mBlockEndAmp;
    double mBlockDeltaAmp;
    double mStep;
};

class MainIPlug;
class Voice;
class EnvelopesManager;

class Envelope : public IControl
{
public:
    bool mIsEnabled = true, mIsBipolar = true;
    unsigned int mLengthInSamples, mLoopLengthInSamples, mSectionLengths[gMaxNumPoints];
    int mIndex;
    double mRate = 1.0, mAmount = 1.0;
    EnvelopesManager *pEnvelopesManager;
    EnvelopeType mType;
    EnvelopeLoopType mLoopType;

    unsigned int mNumPoints, mLoopPointIndex;
    double mLengths[gMaxNumPoints] = { 0.0 };
    double mAmps[gMaxNumPoints];
    double mTensions[gMaxNumPoints - 1];

    double mValue[PLUG_VOICES_BUFFER_SIZE][PLUG_MAX_PROCESS_BLOCK];
    EnvelopeVoiceData mEnvelopeVoicesData[PLUG_VOICES_BUFFER_SIZE];

    Envelope(MainIPlug *plug, EnvelopesManager *envelopesManager, int x, int y, int index);
    ~Envelope();

    void SetSampleRate(double sampleRate);
    void SetRate(double rate);
    void SetType(EnvelopeType type);
    void SetAmount(double amount);
    void SetBipolar(bool bipolar);
    void SetEnable(bool enable);

    void CalculateLoopLength();
    void CalculateSectionsLengths();

    void AddPoint(double position, double amplitude);
    void DeletePoint(int index);
    void SwapPoint(int currentPointIndex, int newPointIndex, int increment);

    void CleanEnvelope();

private:
    double mSampleRate;
    MainIPlug *pPlug;
};

class EnvelopesManager : public IControl
{
public:
    unsigned int mNumEnvelopes, mNumRunningEnvelopes[PLUG_VOICES_BUFFER_SIZE];
    Envelope *pEnvelope[kNumParamsAutomatable];

    EnvelopesManager(MainIPlug *plug, int x, int y, int numEnvelopes = kNumParamsAutomatable);
    ~EnvelopesManager() { }

    void Serialize(nlohmann::json &jsonPlugin);
    void Unserialize(nlohmann::json &jsonPlugin);

    void Reset(int voiceIndex);
    void ProcessBlock(int voiceIndex, int blockSize);

private:
    MainIPlug *pPlug;
};

#endif // !ENVELOPE_H
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to CodeReview.SE! Your questions sounds interesting. Unfortunately, I have the felling we are missing a bit of context here. Could you provide a slightly bigger piece of code that would include definitions of things such as "pEnvelope" ? \$\endgroup\$ – SylvainD Oct 16 '18 at 7:39
  • \$\begingroup\$ @Josay: added ;) Hope its enough! \$\endgroup\$ – markzzz Oct 16 '18 at 7:56
  • \$\begingroup\$ Is double precision required? Vectorization will be more efficient with a narrower type, preferably uint16_t \$\endgroup\$ – harold Oct 16 '18 at 8:29
  • \$\begingroup\$ @harold: yes. Maybe float would change things? I've normalized things between 0 and 1.0 \$\endgroup\$ – markzzz Oct 16 '18 at 8:57
  • \$\begingroup\$ @markzzz float would help but not as much as 16bit fixed-point (of course it can still be between 0 and 1) \$\endgroup\$ – harold Oct 16 '18 at 9:02
3
\$\begingroup\$

Simplify loop

Let's examine your main loop (minus the commented out part):

        for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
            // update output value
            double value = blockStartAmp + (blockStep * blockDeltaAmp);
            values[sampleIndex] = (bp0 * value + bp1);

            // next phase
            blockStep += rate;
        }

You are filling the values array with some computed value, and it requires 3 adds and 2 multiplies per iteration. But if you expand the computation:

bp0 * value + bp1
= bp0 * (blockStartAmp + (blockStep * blockDeltaAmp)) + bp1
= bp0 * blockStartAmp + bp0 * blockStep * blockDeltaAmp + bp1

Note that from one iteration of the loop to the next, the only variable that changes is blockStep, and it changes by rate per iteration. Therefore, the whole value changes by bp0 * rate * blockDeltaAmp per iteration. So if we precompute that delta, we can reduce your loop to this:

        double value = bp0 * ((blockStartAmp + (blockStep * blockDeltaAmp)) + bp1;
        double delta = bp0 * rate * blockDeltaAmp;
        for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
            values[sampleIndex] = value;
            value += delta;
        }

Now your loop only has one addition per iteration, instead of 3 additions and 2 multiplies.

Unnecessary Copy

Currently, you create a temp array, fill it in, then copy to the final destination:

        double values[PLUG_MAX_PROCESS_BLOCK];
        for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
            // ...
            values[sampleIndex] = (bp0 * value + bp1);
        }
        std::memcpy(envelope.mValue[voiceIndex], values, PLUG_MAX_PROCESS_BLOCK);

Instead, you could just write to the final destination directly:

        double *values = envelope.mValue[voiceIndex];
        for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
            // ...
            values[sampleIndex] = (bp0 * value + bp1);
        }

This saves doing the memcpy, which could potentially save a lot of time. If you don't fill the whole buffer and need to zero the part you didn't fill, you can add a call to memset to zero out the rest of the buffer.

Is 3% CPU too much?

You haven't told us what CPU you are using. But here is a rough calculation:

  • Your host sends 48k samples per second in blocks of 256, so it calls your function 48000 / 256 = 188 times per second
  • Within your function, you loop 256 * 16 * 10 = 40960 times. So every second, your inner loop runs 188 * 40960 = 7700480 times.
  • If your inner loop takes 5 clock cycles to run (which is fast), then it will take 7.7M * 5 = 38.5M cycles per second.
  • If your CPU is a 2 GHz processor, this will be 1.925% of your CPU time.

But in the above, the 5 cycle per inner loop number was something I just estimated as a goal to strive for. You are doing one floating point add and one memory write per iteration, and I'm guessing that memory bandwidth might be the limiting factor and not the floating point adds. If that is true, then switching from double to float should really help you because you will be writing half as much memory.

\$\endgroup\$
  • \$\begingroup\$ Nice. I've saved 1% unit of CPU. Still too much imo, no? \$\endgroup\$ – markzzz Oct 16 '18 at 8:57
  • \$\begingroup\$ What setting are you using? try compiling with -02 -03, which will tell your compiler to actually make it fast. \$\endgroup\$ – Oscar Smith Oct 16 '18 at 12:51
  • \$\begingroup\$ @markzzz I don't know if 1% is too much or not. You haven't stated what CPU you are using. Plus, you have a quadruply nested set of loops that iterate remainingSamples * 16 * 10 * blockSize times (16 = voiceIndex, 10 = envelopeIndex). I don't know how big remainingSamples and blockSize are. Obviously you want to make your function as fast as possible, but it may be the case that you are just trying to process too much data on too slow of a CPU. \$\endgroup\$ – JS1 Oct 16 '18 at 19:19
  • \$\begingroup\$ @markzzz I added a second part about not doing the memcpy. And BTW I reread your question and I can see now that you are iterating 256 * 16 * 10 times (40960). So now the question is: how often is this function called? \$\endgroup\$ – JS1 Oct 16 '18 at 19:31
  • \$\begingroup\$ Host sent 48k samples in One seconds, with bunch of 256 (i.e. block size usually is 256, but can be variable). About copy: already tried with pointer, but it seems slower. I think because it swap between RAM on each iteration? \$\endgroup\$ – markzzz Oct 16 '18 at 19:35
3
\$\begingroup\$

16bit fixed-point SIMD

Here is a version adjusted to use 16bit fixed-point arithmetic, this changes the type (and interpretation) of the result, so the code that uses it needs to be adjusted too.

There are some advantages to this:

  • low latency addition, for floating point addition you need multiple accumulators to be able to handle a loop-carried dependency well. So the code ends up being simpler.
  • SIMD is fixed width, so using narrower elements means there are more lanes. For example there are 8 uint16_ts in an __m128i but only 2 doubles.
  • lower memory usage, often a lot of time can be saved just by touching less memory.

SSE2 has decent support for 16bit fixed-point arithmetic, better than C++ itself, so it's generally not that hard to use. It does take a bit more care to ensure that values are used with the right interpretation, which is usually not a concern for floating point code, where the floats are mostly just interpreted "as themselves".

If we have these pre-calculated values

double value = bp0 * ((blockStartAmp + (blockStep * blockDeltaAmp)) + bp1;
double delta = bp0 * rate * blockDeltaAmp;

Then the 16bit fixed-point equivalents calculated from that would be

uint16_t value16 = value * 65536.0;
uint16_t delta16 = delta * 65536.0;

But these turn out not to be super useful, since they end up being multiplied again and it is more accurate to keep that value a double as long as possible. Obviously creating delta16 and then multiplying it by 8 (there are 8 samples per __m128i) would create a value that for sure has its 3 lowest bits zeroed out, but doing that calculation in double precision all the way until the moment it is converted to 16bit fixed-point enables those bits to be non-zero as well if appropriate. These would be useful in scalar code though.

Then for SIMD we need a starting vector,

uint16_t temp[8];
for (size_t i = 0; i < 8; i++)
    temp[i] = round((value + i * delta) * 65536.0);
__m128i vvalue = _mm_loadu_si128((__m128i*)&temp[0]);

And a vector of deltas,

// calculate from delta for extra precision
__m128i vdelta = _mm_set1_epi16(round(delta * 65536.0 * 8));

Then start filling the output:

for (size_t sampleIndex = mblockStart; sampleIndex < mblockEnd; sampleIndex += 8) {
    _mm_storeu_si128((__m128i*)&values[sampleIndex], vvalue);
    vvalue = _mm_add_epi16(vvalue, vdelta);
}

The parameters should not be updated with an if inside this loop, that would evaluate that branch every iteration and no scalar blockStep is available. But it can be done by putting that basic output-filling loop inside an other loop that updates the parameters and then calculates how long the inner loop can run for before the parameters must be updated again.

Ideally the mini-block size (the number of samples between parameter updates) would be a multiple of 8 for obvious reasons, but it does not have to be, as long as there is some padding at the end of the buffer to accommodate the "past-the-end" write of the last mini-block. For mini-blocks other than the last one, writing a little bit of extra data does not matter, the next mini-block will just overwrite it anyway.


Floating point but a bit faster

If that all turns out to be too difficult to work with or too imprecise, here is a basic trick to improve the performance of dependent floating point additions:

double value0 = bp0 * ((blockStartAmp + (blockStep * blockDeltaAmp)) + bp1;
double delta = bp0 * rate * blockDeltaAmp;
double value1 = value0 + delta;
double value2 = value0 + delta * 2;
double value3 = value0 + delta * 3;
double delta4 = delta * 4;
size_t sampleIndex;
for (sampleIndex = 0; sampleIndex + 3 < blockSize; sampleIndex += 4) {
    values[sampleIndex + 0] = value0;
    values[sampleIndex + 1] = value1;
    values[sampleIndex + 2] = value2;
    values[sampleIndex + 3] = value3;
    value0 += delta4;
    value1 += delta4;
    value2 += delta4;
    value3 += delta4;
}
// in case blockSize is not always a multiple of 4
for (; sampleIndex < blockSize; sampleIndex++) {
    values[sampleIndex] = value0;
    value0 += delta;
}

Except on super old CPUs, the main problem with floating point addition is not that it cannot be done often enough, the problem is that it takes a fair amount of time from start to finish. Even a fairly old CPU can start a floating point addition every cycle (some modern CPUs can do two), but the time from start-to-completion of a particular addition is around 3-4 cycles. So in order to not get stuck waiting for the previous addition to complete, the next addition needs to be independent of it.

Since there are 4 independent sums, as long as the latency of FP-add is 4 or less, the example above would be able to complete a value every cycle in the best case (other concerns may slow it down a little), whereas in a simpler loop with only one value-variable the additions queue up and execute one-by-one, head-to-tail, without overlapping each other.

\$\endgroup\$
  • \$\begingroup\$ Nice suggestions! I'll try the second First... But First: is it a good deal for you make a local copy of an array and then reverse it with memcopy? I feel i waste resource there... \$\endgroup\$ – markzzz Oct 16 '18 at 19:26
  • \$\begingroup\$ @markzzz what do you mean by "reverse it with memcopy"? There is no reverse, is there? But yes of course not doing it is less work than doing it \$\endgroup\$ – harold Oct 16 '18 at 19:35
  • \$\begingroup\$ I mean using a local copy and than copy back to object variable (so I can use it later). I need to "store" processed data :) \$\endgroup\$ – markzzz Oct 16 '18 at 19:37

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.