Hacker News Reader

Comment by iammyIP | Hacker News Reader

To be flexible without if / else or switches. If i want a multi-oscillator that can produce different waveforms i use a pointer to different functions depending on the waveform i need. Same goes for different postprocessing / routing. I didn't actually profile this compared to a switch, but for me it's cleaner and more modular. If you got a static effect whose routing stays the same you don't need it of course.

edit: i've never used a virtual method, but my impression is that performance-wise it's quite different to pointers to simple functions. most of my audio code is pod-structs to layout the data in the order that it gets acessed and standalone functions that then modify stuff in the structs. it's pretty barebones data oriented programming compared to the other extreme, some baroque meta virtualised oop architecture.

View on HN

Runtime codegen could make a big difference. You can dynamically build your processing pipes without overhead. No function pointers needed, total flexibility.

Check JIT libraries (like GNU lightning) and LLVM. Also LuaJIT might be interesting.

"llvmpipe", software rasterizer that uses LLVM for runtime codegen for shaders: http://www.mesa3d.org/llvmpipe.html

sounds intriguing and way more flexible, but the example is for video? i don't know anything about this, but if i had to guess i would say that any runtime code generation is worse performance wise compared to a mix of pod structs and function pointers to functions which are all known at compile time.

> runtime code generation is worse performance wise compared to a mix of pod structs and function pointers to functions which are all known at compile time

Having "a mix of pod structs and function pointers" is analogous to having an interpreter for some scripting language. Do you consider interpreted scripting languages fast?

Interpreters are slow pretty much for that reason. Having to chase pointers.

Runtime code generating JITs wipe floor with interpreters, being usually 10-100x faster.

Now I'm not saying your application will be 10-100x faster, but done right, it'll absolutely be faster if your performance critical "inner loop" / filter chain needs to currently follow pointers. It's just a question of how much and whether it matters for the use case.

[Having "a mix of pod structs and function pointers" is analogous to having an interpreter for some scripting language.]

Yes, it might be similar at the core, but i would guess the usual audio pod-struct/function mix is many times less complex than a full jit language interpreter.

What does chasing pointer mean to slowness then? My understanding is that its similar to data pointers, that a certain region of memory needs to be looked up and be fed into the instruction cache. If the process is layed out so that instruction cache misses are minimised, whats so bad about it?

> whats so bad about it?

Other than executing a lot of useless instructions, causing pipeline stalls due to indirection, potentially mispredicted branches, etc. I guess nothing.

Just remember if the actual operation is just a few instructions, the price for all that extra work can be 1-2 orders of magnitude.

If you only need to chase pointers say a million times per second or less, go for it. It won't matter so much. In worst cases you might lose 10% (of total cpu core capacity) performance, if even that. If it's in tens of millions or more, it's pretty likely to be a significant bottleneck.

What does your profiler say? What kind of ILP you're getting?

The current code with the function pointers and pods works ok for me, its about in the million per second range and i didn't profile any alternative to it. How would you implement such an alternative with jit code generation into this pod/function c code setup without major rewrites? Seems to me like a completely different system which is bound to llvm (i use gcc)?

edit: since you were mentioning jit optimisation and code generation - this is a field i do not have any experience, but my impression so far is that this runtime re-arrangement of code can yield quite a big performance increase for higher level languages (jvm does this afaik). Is the link you provided the same idea for statically compiled c/c++ code?

If the chain of operations change rarely, you might even get away with calling clang or whatever compiler and actually compiling a chain of filter source code mashed together.

So how would you raw-structure a performance critical (audio) program that needs some flexible path for the data processing, like with a 128 sample buffer and about 3-10 choices along the processing path. Processing path should be switchable per buffer frequency. The function pointers were the best solution i could come up with, but maybe that doesnt really eliminate branching cache misses and stalling and its impact on performance, but just hides it in plain-text.

How many permutations? If not too many, maybe just compile them all.

Sometimes you do need to use function pointers. It's just if it's in a performance critical path, you might want to consider alternatives.

Permutations are for my own case pretty low, it's just a replacement for a handful of switches, otherwise the flow is pretty straightforward. But i see that if one wants to restructure the whole program flow on-the-fly it might lead to problems. What are the alternatives? The link you provided is for graphics, and does not seem to be generalised. Do you suggest a complete switch to a jit interpreted codebase?

Graphics and audio are usually pretty similar, other than the volume of data is usually quite a bit larger for graphics than for audio.

There's no silver bullet how to structure such flexible, dynamically configurable high performance system.

I disagree with 'pretty similar' and would suggest 'challenging in completely different ways'. Graphics in a minimum 60 fps context is about 700 times less time sensitive. That's almost three magnitudes difference. On top of that it isn't a major fail if you don't meet the 60 on time, but in audio it is. Furthermore audio tends to be more single thread focused, while graphics is much more multi thread friendly (see your link to llvmpipe and general gpu architectures). Graphics need to shovel around about some hundreds of megabytes per second and is less time critical, whereas audio is ultimately time critical and only needs to produce about 350kb per second for 32 bit stereo (the data difference you already mentioned). That's again some three orders of magnitude of difference. I wouldn't call that similar. Since you can't provide any advise for an alternative to function pointers i must challenge your expertise in audio programming since you seem to project your view from a graphics programming point.

Well, I haven't done audio programming for quite a while. I did get audio hardware behave pretty nicely in 1998, though. I believe low latency audio was much harder back then.

I'm pretty surprised if your deadline is really that 23 microseconds (60 fps / 7000). You can't even reliably dispatch an IRQ request in that time!

> I wouldn't call that similar

If you have a long audio filter chain it's not all that different from a long fragment shader. You can think of a fragment shader as a filter chain.

> Since you can't provide any advise for an alternative to function pointers

Uh. That's pretty hard without seeing the source code and full problem description. Especially because you seem to be expecting some magical solution. Well, those don't exist, it's just hard work.

Besides, like I said earlier, sometimes function pointers are appropriate for the task. Just understand the cost. Do keep in mind audio filter chains can be pretty complicated. If your filter chain has many concurrent channels with hundreds of dynamic filter steps for each sample to pass through, yeah, you might have some performance problems.

> i must challenge your expertise in audio programming since you seem to project your view from a graphics programming point.

Be my guest. Just wanted to share something I know about and give new ideas. Btw, I'm not doing graphics, but mostly I/O with micro/millisecond level deadlines.

Getting audio hardware to behave nicely for audio is pretty nice :) The calculation for the time factor difference is simply 44100/60 which is about 733, i don't know how the 23 microseconds you got there relate to this.

Your comparision to graphics seem to relate to long FIR filters, which i dont't use because of cache reasons (big kernel/lookup table). FIR filters can however sound pretty nice with static parameters but get extremely expensive for realtime modulation. For realtime modulation i suggest IIR filters (Finite Impulse Response vs Infinite Impulse Response filter architecture).

Of course it's hard to give advice into the blue without any source, but i atleast expected some general hint, like 'avoid branches, use function pointers' on a next-level, since you were so opposed to function pointers to begin with.

I am also not completely sure what's the best approach in this regard, and i surely did not enough profiling in this regard.

That said, i remain sceptical regarding your critique of function pointers in a single threaded audio application, because of a lack of an alternaltive.

I/O on a microsecond critical deadline certainly seems to be in a neigbourhood to these problems. Do you use some arcane javascript asm.js with some jit auto-reconfiguring optimising for this, or how would you describe your approach?

> i don't know how the 23 microseconds you got there relate to this

1 / (60 Hz * 700) = 23.8 microseconds. (Yeah, should have rounded up to 24).

What worked for me in the past was just concatenating (well, memcpying) executable filter blocks of x86 code while ensuring parameters were in the right registers.

Loop start block -> filter 1 -> filter 2 -> filter 3 ... -> loop end block.

I made these blocks by processing specifically compiled (not at runtime, but ahead of time) functions, stripping prologues and epilogues. There's more to it, but it's been a while.

Crude, but effective and fast even when each filter step was pretty small on its own.

So you put in the parameters into registers 'per hand' in assembly and then memcopyed some function to the right adress (using a function pointer?) to process these registers? Wow. That sounds pretty complicated. For now i just use gcc and function pointers and let gcc do the rest.

About the 1/(60 * 700) what does that number even mean to you? 1/60 is the usual refresh rate in seconds, about 16 ms, why do you multiply this with 700, this makes no sense?

You said earlier:

> Graphics in a minimum 60 fps context is about 700 times less time sensitive.

16.6 ms (60 fps) / 700 = ~24 microseconds.

> So you put in the parameters into registers 'per hand' in assembly and then memcopyed some function to the right adress (using a function pointer?) to process these registers? Wow. That sounds pretty complicated. For now i just use gcc and function pointers and let gcc do the rest.

I concatenated blocks of compiled code together (compiled as position independent), avoiding branches and indirect calls.

Loop setup block took care of putting right parameters to right registers.

Hardest part was getting the filter parameter passing right. Dynamic configuration was trivial after that.

There were no function pointers except one to trigger the top level loop.

My original calculation was that in audio you need to deliver 44000 values per second, in graphics you need 60 - 44000/60 roughly equals to 700. That's the difference factor :) (of course the data volume per delivery and it's techniques differ much, thats why i suggested that these are very different problems) It's very simple, maybe we got caught up into some misunderstanding.

For your concatenated blocks of precompiled code maybe you should have used simple function pointers, and one monolithic precompiled block to achieve the same result like i originally suggested.

> For your concatenated blocks of precompiled code maybe you should have used simple function pointers, and one monolithic precompiled block to achieve the same result like i originally suggested.

That's how the original version was like, but it was way too slow. I achieved eventually about 10x faster performance for typical (dynamic) configurations.

Unless you don't provide a code example and/or dev chain description i'm unable to follow you.

Unless your hardware has to be fed sample-at-a-time, your deadline isn't 700 times worse. A fairer comparison would point out for HD video, you have mere nanoseconds per pixel, vs. microseconds for audio samples.

That is, my laptop has ~43 cycles to get out all channels of each pixel, vs. more than 60,000 cycles to get out all channels of each 44.1kHz audio sample.

But the pixels only have to be delivered by screen refresh, and the samples only have to be delivered before the sound card tries to play them--probably 64-1024 samples (or further) in the future.

> Interpreters are slow pretty much for that reason. Having to chase pointers.

Here's a test I did on the Raspberry Pi 3 (with source so anyone can repeat it on more Intel-y hardware): https://gist.github.com/LnxPrgr3/31eaf5648a9956f5c576f70d876...

Calls through a function pointer are technically more expensive, but it's a factor of ~1.1, not 10-100.

Interpreters are slow because they chase pointers and otherwise branch in a manner the CPU can't predict. Calling the same function through the same pointer over and over again isn't that.

Different compilation unit prevents inlining. Function pointers to small functions can be a performance problem for exactly that reason -- except for very specific special cases (when compiler can actually figure out your function pointer calls always end up calling same function), function pointer calls cannot be inlined.

C/C++ compiler abstracts the difference between inlining and actual call. For best results, cross compilation unit optimizations should be enabled so that inlining can occur across object and library boundaries.

> Interpreters are slow because they chase pointers and otherwise branch in a manner the CPU can't predict. Calling the same function through the same pointer over and over again isn't that.

A lot of function pointer usage is also data dependent. Data dependency and too complicated dependency chains are what breaks prediction.

Data-dependent audio pipeline callbacks? In the schemes I'm aware of, they rarely change after setup--hence my thinking effectively fixed targets were the representative case. (After an update, pipeline stalls plague you until the predictor catches up.)

Breaking inlining is probably the real cost to this. Still, we're talking ~9 cycles per indirect call on this hardware. If you call each callback per buffer instead of per sample (which everyone seems to do), you're down to an amortized cost below 1 cycle per sample for a filter chain 14 deep with only 128 sample buffers. 14 filters probably swamp that cost.

Edit: A good compiler will completely remove my trivial function if it's inlined into call.cc's code. It has no side effects, and neither does the loop calling it 100,000,000 times. The resulting timings would be meaningless: doing nothing is cheap!

> Still, we're talking ~9 cycles per indirect call on this hardware.

In 9 cycles, you could execute up to 18 SIMD instructions, each operating on 256 bits worth of data.

For scalar, 9 cycles can be up to 30 instructions or so. For good code, average about 15-20.

> If you call each callback per buffer instead of per sample (which everyone seems to do), you're down to an amortized cost below 1 cycle per sample

Function pointers are perfectly ok even in high performance programming, if it's not what burns the cycles. If you can batch the filter, all is good. If you can't, well, you might need to think up some other solution.

Profiling rocks. I did simply some experimental cases where I ran same test setup with dynamic function pointers and hardcoded code. I quickly noticed that hardcoded version was over an order of magnitude faster. I figured out a way to narrow the difference and ended up doing dynamic code generation.

> doing nothing is cheap!

Code you don't need to run is the fastest code you can have. Infinitely fast in fact.

Its ancient now, but I built exactly this using Ruby and an LLVM wrapper.

https://github.com/jvoorhis/siren

I wouldn't expect this to run on the latest LLVM without a little hand holding (the most painful part was porting it to run on x86_64 after developing it on my white MacBook!) But it worked rather well and was a fun platform for experimenting with composition, synthesis and compilers!

Reply on news.ycombinator.com