2

First, in tuning a frequency analysis function using the Accelerate framework, the absolute system time has consistently been 225ms per iteration. Then last night I changed the order of which two of the arrays were declared and suddenly it went down to 202ms. A 10% increase by just changing the declaration order seems insane. Can someone explain to me why the compiler (which is set to optimize) is not already finding this solution?

Additional info: Before the loop there is some setup of the arrays used in the loop consisting of converting them from integer to float arrays (for Accelerate) and then taking sin and cos of the time array (16 lines long). All of the float arrays (8 arrays x 1000 elements) are declared first in the function (after a sanity check of the parameters). They are always declared the same size (by a constant), because otherwise performance suffered for little shrinkage of the footprint. I tested making them globals, but I think the compiler already figured that out as there is no performance change. The loop is 25 lines long.

---Additions---

Yes, "-Os" is the flag. (default in Xcode anyways: Fastest, Smallest)

(below is from memory - don't try to compile it, cause I didn't put in things like stride (which is 1), etc. However, all of the Accelerate calls are there)

passed parameters: inttimearray, intamparray, length, scale1, scale2, amp

float trigarray1[maxsize];
float trigarray2[maxsize];
float trigarray3[maxsize];
float trigarray4[maxsize];
float trigarray5[maxsize];
float temparray[maxsize];
float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

vDSP_vfltu32(inttimearray,timearray,length); //convert to float array
vDSP_vflt16(intamparray,amparray,length);    //convert to float array

vDSP_vsmul(timearray,scale1,temparray,length);    //scale time and store in temp
vvcosf(temparray,trigarray3,length);     //cos of temparray
vvsinf(temparray,trigarray4,length);     //sin of temparray
vDSP_vneg(trigarray4,trigarray5,length); //negative of trigarray4

vDSP_vsmul(timearray,scale2,temparray,length); //scale time and store in temp
vvcosf(temparray,trigarray1,length);           //cos of temparray
vvsinf(temprray,trigarray2,length);            //sin of temparray

float ysum;
vDSP_sve(amparray,ysum,length);    //sum of amparray

float csum, ssum, ccsum, sssum, cssum, ycsum, yssum;

for (i = 0; i<max; i++) {

    vDSP_sve(trigarray1,csum,length);    //sum of trigarray1
    vDSP_sve(trigarray2,ssum,length);    //sum of trigarray2

    vDSP_svesq(trigarray1,ccsum,length); //sum of trigarray1^2
    vDSP_svesq(trigarray2,sssum,length); //sum of trigarray2^2

    vDSP_vmul(trigarray1,trigarray2,temparray,length); //temp = trig1*trig2
    vDSP_sve(temparray,cssum,length);                  //sum of temp array
    // 2 more sets of the above 2 lines, for the 2 remaining sums

    amp[i] = (arithmetic of sums);

    //trig identity to increase the sin/cos by a delta frequency
    //vmma is a*b+c*d=result
    vDSP_vmma (trigarray1,trigarray3,trigarray2,trigarray4,temparray,length);
    vDSP_vmma (trigarray2,trigarray3,trigarray1,trigarray5,trigarray2,length);
    memcpy(trigarray1,temparray,length*sizeof(float));
}

---Current Solution---

I've made some changes as follows:

The arrays are all declared aligned, and zero'd out (I'll explain next) and maxsize is now a multiple of 16

__attribute__ ((align (16))) float timearray[maxsize] = {0};

I've zero'd out all of the arrays because now, when the length is less than maxsize, I round the length up to the nearest multiple of 16 so that all of the looped functions operate on widths divisible by 16, without affecting the sums.

The benefits are:

  • Slight performance boost
  • The speed is nearly constant regardless of order of array declaration (which is now done right before they are needed, instead of all in a big block)
  • The speed is also nearly constant for any 16-wide length (i.e. 241 to 256, or 225 to 240...), whereas before, if the length went from 256 to 255, the function would take a 3+% performance hit.

In the future (possibly with this code, as analysis requirements are still in flux), I realize I'll need to take into consideration stack usage more, and alignment/chunks of vectors. Unfortunately, for this code, I can't make these arrays static or globals as this function can be called by more than one object at a time.

4
  • 1
    Are you able to get back to the 225ms by just swapping the array declaration order back?
    – Dan F
    Aug 10, 2012 at 13:18
  • Yes, with those two, consistently. And I found that if I switch other arrays, I can end up with even worse performance 290+ms or in other configurations 210ms. Right now they are all declared in a block of lines (one per line, to make testing the order quicker). However, I did attempt moving each declaration to right before it was needed, and got the 290ms.
    – Adam Jones
    Aug 10, 2012 at 13:23
  • 2
    Maybe show us the code? At least for the declarations, if they are all together. Aug 10, 2012 at 13:26
  • Could it be some caching thing? With the arrays in one order, perhaps you are more likely to pull in data in one operation that you will need in the next operation.
    – JeremyP
    Aug 10, 2012 at 14:44

5 Answers 5

3

The first thing I would suspect is alignment. You may want to experiment with:

__attribute__ ((align (16))) float ...[maxsize];

Or make sure that maxsize is a multiple of 16. That could definitely cause a 10% hit if in one configuration you're aligned and in another you're not. Vector operations can be extremely sensitive to this.

The next major issue you may have is a huge stack (assuming maxsize is fairly large). ARM can deal with numbers less than 4k much more efficiently than it can deal with numbers larger than 4k (because it can only deal with 12-bit immediate values). So depending on the how the compiler has optimized it, pushing amparray way down on the stack could lead to more complicated math to access it.

When small twiddly things lead to big performance changes, I always recommend pulling up the assembly (Product>Generate Output>Assembly) and seeing what's changes in the compiler output. I also highly recommend Whirlwind Tour of ARM Assembly to get you started understanding what you're looking at. (Make sure you set the output to "For Archiving" so you see the optimized result.)

You should also do a few more things:

  • Try rewriting this routine as simple C instead of using Accelerate. Yes, I know Accelerate is always faster, except it's not. All those function calls are quite expensive, and the compiler can often better vectorize simple multiplication and addition that Accelerate can in my experience. This is particularly true if your stride is 1, your vectors are not enormous, and you're on a 1-2 core device like an iPad. The moment you have code that handles a stride (if you don't need a stride), it's more complicated (slower) than the code you would have written by hand. In my experience, Accelerate does seem to be very good at ramps and transcendentals (cosines of big tables for example), but not nearly so good at simple vector and matrix math.

  • If this code really matters to you, I've found that hand-writing the assembly can definitely out-pace the compiler. I'm not even that good at ARM assembler, and I've been able to beat the compiler by 2x on simple matrix math (and the compiler crushed Accelerate). I'm particularly talking about your loop here that seems to be doing just adds and multiplies. Handwriting the assembly is a pain of course, and you then have to maintain a C version for the assembler, but when it really matters it's really fast.

3
  • Recently I changed my analysis blocks, and realize now I could decrease maxsize considerably - which may make this a useless exercise. Originally all of the code was in straight C, and was easily 10x slower than when I replaced it with Accelerate (vdsp_vmma and vvsinf are vastly faster than C) - again when the blocks were larger, and the iterated array lengths and index were variable (neither are true now). The timing I have now is acceptable, and I'm not sure ASM would be worth the time. However, I am curious about the alignment -I have tried that attribute to no effect. Any thoughts on this?
    – Adam Jones
    Aug 10, 2012 at 15:40
  • Thanks for the note on vdsp_vmma. I definitely agree about vvsinf; had not profiled vmma. Alignment doesn't always win if the data is already aligned (which can happen by accident or optimization), or if the particular function doesn't rely on it too much. Sometimes they do a separate iteration to handle the leading unaligned values until they can get onto aligned data. Sometimes they just don't require aligned data.
    – Rob Napier
    Aug 10, 2012 at 16:44
  • Thank you. I'll give aligning another shot, and playing with maxsize. The whole reason I went to Accelerate was the block size was -huge-. And I was just spending too much time iterating. Now that that I've headed to a smaller block, straight C may be faster without the overhead. However, I won't remove it now, as it makes the function more readable (again, not all of my code is shown - but the missing lines are all simple arithmetic).
    – Adam Jones
    Aug 10, 2012 at 17:05
2

Without runnable code, it can be difficult to determine what performance impediments there are.

I am going to use this answer to suggest some possibilities and comment on some of the issues raised in other answers and comments to this question.

First, with 7 arrays of 4 kB each, you are using nearly the size of L1 cache. Depending on how much else is used by the stack and such, you could be thrashing the cache. This could explain why reducing the block size improved performance: With smaller blocks, less memory was used in each iteration, and all of it fit in cache, so little or nothing was cast out during an iteration. Another way to deal with this sort of cache thrashing is strip mining: Instead of performing sve, svesq, vmul, vmma, and memcpy on the entire length, perform all of them on a portion of the length (e.g., half), then perform all of them on another portion, and repeat as necessary until they have been entirely processed.

trigarray5 only exists so that the second vmma negates trigarray4. Eliminate trigarray5 and call vmmsb (subtract instead of add) with trigarray4. This also reduces memory use.

Cache geometry sometimes causes thrashing to occur even when less data than fills cache is used. Cache is partitioned into sets, and each memory address must be mapped to a particular set. E.g., a cache with 32,768 bytes may have 1024 “lines” of 32 bytes each, but it may be organized into 256 sets of four lines. Any one memory address maps to one set, and it must use one of the four lines in that set. If you have five arrays that start at the same address modulo this geometry (or that substantially overlap), then they will contend for the four lines in each set, casting each other out as they go. This is avoided when arrays are allocated consecutively in memory, as the compiler commonly does when arrays are simply declared one after the other, but there can be complications. Without runnable code, it is hard to determine.

Aligning the arrays to multiples of 16 bytes is fine and may help slightly. In certain situations, it helps a lot. When possible, many vDSP routines do process a few initial elements to reach a well-aligned boundary and then uses fast SIMD code until near the end of the array, when another few elements may need to be processed individually. However, this is not always possible, as when a routine that operates on multiple vectors is passed vectors with different alignments. (Processing elements to align one pointer leaves other pointers misaligned.) Besides adding the align attribute, another way to align arrays is to allocate them with the standard memory allocation routines, such as malloc. On Mac OS X and iOS, malloc returns 16-byte aligned addresses.

The stack size and the fact that ARM has limited immediate values is likely not an issue, the calculation of vector addresses should be a trivial portion of the computation in your code. (Also, ARM has some interesting flexible immediate values, not simply 12-bit integers.)

The cost of the actual function call and return itself is likely trivial. The Apple-supplied compilers do not “better vectorize simple multiplication and addition than Accelerate can,” and function calls are not “quite expensive.”

You omitted the strides. If they are not one, you will likely gain a lot by rewriting your code so that the data has unit stride when the vDSP routines are called.

Branch prediction is likely not a problem here.

Runnable code would help hugely in diagnosing your performance issues.

3
  • For future reference to others, I didn't use vmmsb because it is significantly slower than creating a negative array and using vmma. I hadn't thought of doing chunks at a time - that would be a good idea for huge vectors. I can see from your response, and others, that in the future I need to be much more concerned with memory usage than I have been before.
    – Adam Jones
    Aug 11, 2012 at 14:18
  • The performance of vmmsb and vmma should be identical in current versions of iOS. (The source code appears to be identical except for changes of add to subtract.) On Mac, vmma is optimized and vmmsb is not. That is an oversight; please file a request at bugreport.apple.com to optimize vmmsb. If you saw ARM performance drop, it may be an illusion, due to the other effects discussed. If it is reproducible, please file a bug report, and indicate specific versions of software, particularly the target OS version and the device model. Aug 11, 2012 at 18:08
  • You are right. I was testing the functions inside a bare Mac app. However, I just tested it in a bare iOS app on both the simulator and my phone. On the simulator I get about a 40% slowdown with vmmsb (it's not this bad on the Mac app), and on the iPhone the performance is exactly the same. Thanks, you saved me some memory.
    – Adam Jones
    Aug 12, 2012 at 0:12
0

Probably something to do with Branch Prediction and what elements are inside your arrays.

See this post for an AWESOME reference. Your post could be similar to this post in that by declaring your arrays in one order, the data appears "sorted", but in the other order, it is not.

Why is it faster to process a sorted array than an unsorted array?

5
  • There are no IF statements anywhere in that code. As I understand it, without conditionals, there's nothing to branch. As an aside, I've tested adding the __property___((aligned)) for the Accelerate arrays but it seems the compiler has already aligned them.
    – Adam Jones
    Aug 10, 2012 at 14:36
  • 1
    You absolutely have a branch. It's in the for(). I'm not saying branch prediction is your issue, but there's certainly a conditional that gets called max times.
    – Rob Napier
    Aug 10, 2012 at 14:46
  • Branch prediction on the for is likely trivial in this case because it would be swamped by the work in the vDSP routines. Even if the branch for the for falls out of the branch history cache and is mispredicted every time, it should not affect performance that much. Aug 10, 2012 at 23:08
  • Changing the order of arrays does not change the sorting of items inside the arrays.
    – Krazy Glew
    Aug 12, 2012 at 0:58
  • Of course. I didn't really read the question that carefully and had just read the thread I linked, and it sounded like a possible cause. After actually looking at Adam's code, I see that branch prediction had nothing to do with it.
    – MikeS
    Aug 14, 2012 at 17:40
0

Just a guess here. Alignment?

Those libraries are supposed to use SIMD instructions, and the timing of these are dependent on alignment even in some cases where alignment is not required.

Also cacheline alignment may or may not play a role.

Those arrays are allocated on the stack, meaning that you have little control on the alignment of that data beyond the sizeof(float) intrinsic guarantee and the architectural guarantee for the first object (64 bits alignment is de facto guaranteed for the first local variable if you compile in 64 bit mode).

You may try to verify what the data alignment is by printing/logging the addresses. And to play around with the timing effects of alignment by defining a structure to hold the data and using malloc to get memory for it (get more memory than you need so you can place the structure at different offsets in the memory block, especially if you want to play with cacheline alignment).

0

First: this sort of sensitivity to data placement is unfortunately common. Some of us have written code that tries multiple different layouts

The usual culprits for performance losses such as this are:

  • branch mispredictions

  • cache effects

    • capacity misses (just plain too much data e.g. 1MB of data does not fot in a 32KB cache)

    • cache conflicts (e.g. more than 4 addresses that are the same modulo 8K in a 4-way associative 32KB cache)

  • DRAM effects

    • DRAM page misses

I am having trouble parsing what you say: what is MAXSIZE? You say 7*4KB... But you have 8 arrays, so I doubt that you are saying that MAXSIZE=1024. Are you saying that MAXSIZE is 7*1024? (* 4B / float?)

Anyway: if MAXSIZE for each individual array is circa 28KB, then you are near cache size for many systems. In this case, I would suspect DRAM page effects - I would suspect that the good performing arrangement puts the most accessed array in a separate DRAM page.

You don't say which performs better, but I would guess:

float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

eyeballing your code, timearray seems to be most accessed. If the performance is better with timearray second, and my guess about MAXSIZE is correct, then I would bet that it is DRAM page effects.

Quick explanation: DRAMs have concepts of pages and banks. Not to be confused with OS pages. Eac DRAM chip, and hence each DIMM, has 4 or 8 internal banks. Each bank can have one open page. If you access data from the same page, same bank, it is fastest. If you access data frm the alread open page in a different bank, fast, but slower than same page same bank If you need a different page in the same bank, really slow. If you have a writeback cache the writeacks ocur almost at random, so you can get really bad page behavior.

However, if I have guessed wrong about MAXSIZE, then probably a cache effect.

RED FLAG: you say "I didn't put in things like stride". Strides are notorious for making data behave poorly in the cache. Caches are typically set asociative, meaning that they have what I call "resonance" - addresses that are the same modulo the resonance of the cache will map to the same set. If you have more such than the associativity, you wll thrash.

Calculate the resonance as the cache size divided by the associativity. E.g. if you have a 32K 4-way associative cache, your resonance is 8K.

Anyway... if you are only accessing things on a stride, then array placement can matter. E.g. say that you have a stride of 16. I.e accessing eements 0, 16, 32, 48 etc. If MAXSIZE was 7*1024, as I guessed above, then elements

float trigarray1[maxsize];
float trigarray2[maxsize];
float trigarray3[maxsize];
float trigarray4[maxsize];
float trigarray5[maxsize];
float temparray[maxsize];
float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

then the following arrays will conflict - their strided access patterns will map to the same sets:

trigarray1, trigarray5
trigarray2, temparray
trigarray3, amparray
trigarray4, timearray,

if you interchange amparray and timearray, then

   trigarray3 will conflict with timearray
and
   trigarray4 with amparray

trigarray4 and timarray seem to be the most used, so I am guessing, if you have a stride like 0, 16, 32, 348, or indeed any stride beginning with 0, then those two arrays conflicting are your problem.

However, you might have different stride patterns: 0, 16, 32, 48 ... in one array, and 1,17,33,... in the other. Then different pairs of arrays would conflict.

--

I don't have enough info to diagnose your problem here.

You might be able to do it yourself if you have access to good performance tools.

E.g. on Intel processors, you could record what I call a cache miss profile record the ideally physical memory addresses, compute what sets they map to in the cache, and generate a histogram. If you see spikes, that's likely a problem. Similarly, you can generate DRAM page miss or bank miss profiles. I only mention Intel because I designed some of the hardware to enable this sort of performance measurement. The same sort of thing may be should be, available on ARM (if not, maybe I could get rich selling tools to do it... :-) ).

If these are the problem how can you fix it?

Well, by trying different placements, as you explain above. This can help both strides (cache set conflicts) and DRAM page problems.

If strides are a problem, you might try making the array sizes a bit dfferent - MAXSIZE + 4, MAXSIZE 8, etc. This can effectvely offset the strides. (It's common in supercomputer codes to see arrays of size 255 or 257, for same reasaon of offsetting strided access patterns so as not to conflict.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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