On Jun 17, 2004, at 7:25 AM, Tim Goetze wrote: Is this code publicly available? What algorithms are you using for your lock-free fifos? One thing I am still looking to learn more about is how to adjust thread priorities and such to make sure that your threads are run often enough (especially the disk thread), and how to decide how big your disk buffers need to be. Josh

Paul Davis wrote: I recently made more tests (I'll release benchmarking code, when it's cleaned up a bit) and it seems that on decently fast disks, like the 7200rpm IDE disks (my Maxtor 80GB IDE disk does up to 40MB/sec sustained), if there is a lot of seeking (which HDR apps like ardour and disk based sampling apps like LinuxSampler do), you need to read more, like 512KB - 1MB at time, because the disk seek time is relatively high (12-14msec) vs the transfer rate (40MB/sec). This means if the buffers are too small then you have lots of disk seeks between reads and you loose performance my benchmark does the following: creates 4 files of 750MB each (3GB total), then seeks around randomly in all 4 files simultaneously and reads 2 bytes after each seek (just to ensure that the disk scheduling algorithm will not fool us). Of course there is still the file cache that could inflate numbers but if the file sizes are big enough (so that they don't fit in RAM) and provided you do thousands of seeks you get quite realistic values that reflect those achieved by a HDR , disk sampling app: for example these are the numbers of my Maxtor IDE 40GB 7200rpm seeks/sec=75.5 average seek time=13.2 msec in the streaming test I read a chunk of X KB from each of the 4 files while(1) { file1.read() ; file2.read() ; file3.read() ; file4.read(); } this causes the disk head seeking beetween the files after each read, just like a HDR app does when reading tracks. these are the numbers I get (read speed). streaming with 128 KB buffers .... performance: 8.50 MB/sec stereo voices at 44.1kHz = 50.53 required memory for buffering: 6.32 MB streaming with 256 KB buffers .... performance: 14.43 MB/sec stereo voices at 44.1kHz = 85.79 required memory for buffering: 21.45 MB streaming with 512 KB buffers .... performance: 21.10 MB/sec stereo voices at 44.1kHz = 125.41 required memory for buffering: 62.71 MB streaming with 1024 KB buffers .... performance: 28.49 MB/sec stereo voices at 44.1kHz = 169.38 required memory for buffering: 169.38 MB streaming with 2048 KB buffers .... performance: 32.88 MB/sec stereo voices at 44.1kHz = 195.44 required memory for buffering: 390.87 MB As you can see the performance increase between 512KB and 1MB is still very big , around 35% , so reading 256KB at time is definitively too little these days. Paul, does ardour allow to specify the size of the per-track-buffers you use for disk streaming, if yes perhaps you should add this as an option since it's handy for the user having the possibility to increase the default values to achieve optimal track count. For example using large RAID arrays, the difference between seek time and raw disk tranfer speed gets even bigger so even bigger buffers are needed to achieve the max track count. (keep in mind I'm not familiar with the ardour codebase nor with advanced settings so my question might be redundant in case ardour already supports it) Joshua: if you want an easy to use Lock-Free FIFO template in C++ look at RingBuffer.h in the LinuxSampler CVS We use this template heavily. For example we set up a large ringbuffer for streaming the audio from disk (one ringbuffer for each voice). The disk thread reads directly into the ringbuffer and the audio thread fetches the data in a lock-free way. This ensures zero-copy operation. Plus we added a wrap space so that a section of the beginning of the buffer is replicated after the official upper bound so that the audio thread can read a bit past of it and still gets the correct audio data (as it was linear), this speeds up the audio interpolation since for the audio thread it's like reading from a linear segment, no nasty if() checks etc, it's all done (from time to time, so no pratical CPU overhead) when the disk thread writes the data to the ringbuffer. But we don't use the lockfree ringbuffer only for audio: we use it (since it's a template you can create ringbuffers of any kind of struct) to send commands between the midi thread (note on/off etc) and the audio thread and to send commands to the disk thread (start/stop streams). Works really well and the resulting code is clean too. The RingBuffer class uses atomic_*() macros so it is safe on any architecture (but on most 32bit word accesses are atomic anyway so the macros simply translate to load and store ops, afaik the SPARC SMP is one of the only archs that needs special care, (and can access only 24bit atomically, thus your ringbuffers are limited to 16million elements). PS: about disk streaming benchmarks ... I ported my benchmark to win32 too and make some tests there too, the irony is that using buffered I/O when lots of disk seeks occur you get really sucky perforomance, as low as 30% of the normal sustained disk transfer speed. It seems that the read ahead algorithm reads too much and get the disk head scheduling wrong (I used Win XP so I assume it has the most performant file I/O among the windows family). Using direct I/O (without buffering) you get decent performance, but you lose the benefits of the file cache. For example in the case of a disk based sampler where you often hit the same notes (thus audio files) over short periods of time you can save lots of accesses. The Linux file cache does an excellent work here. I guess those windows based disk sampler all implemented their own file cache, while on linux the OS does all the work for you :) cheers, Benno http://www.linuxsampler.org

until you want to start processing the data but keep the original around. i was always attached to the zero-copy model, but it just doesn't seem to pan out in real life. i still don't understand this. you can easily construct a worst case scenario where the reader needs to read just a tiny amount from the "end" of the buffer and the rest from the front. in this, it seems to me that your "wrap" space actually has to be the same size as the buffer itself - i.e. you're actually writing two copies of the data. when you use varispeed in ardour, its very easy to make this situation occur. i handled it a different way, one that is less demanding on memory usage that a double-sized ringbuffer because reads are limited to the process() blocksize. --p

Paul Davis wrote: I don't know how ardour works internally, so in your case it might not work but for example the case of LinuxSampler we simply do disk thread fills ringbuffer audio thread reads from ringbuffer applies some DSP processing (envelopes,filter etc) and then sends the data to the audio card. In that case we can operate completely lock-free. There is no worst case and the overhead of our mechanism is very small. It works like that: |------ official ringbuffersize (2^n) ------ | ---- wrap space ---| diskthread: while(1) { - figure out available bufferspace to ringbuffer end (which includes wrap space) - read() from disk directly into the ringbuffer (starting from ringbuffer.write_ptr) memory till you fill the above amount - after the read a ringbuffer macro is called which takes care to mirror the part of wrap space to the buffer beginning via memcpy() (so no duplicate read()s from disk needed) } audiothread: while(1) { sample_t *sample=ringbuffer.read_ptr; process samples beginning at "sample" write data to the audio card increase the read_ptr in the ringbuffer } basically thanks to the wrap space the code in the audiothread can treat the sample[] array like a linear array of samples, it does not know anything about wrapping etc. the only thing needed over linear reads is the increase of the read_ptr, basically read_ptr = (read_ptr + samples_read) & (ringbuffer_size -1) as usual. How to dimension the wrap space so that we avoid that the audio thread accidentally oversteps over buffer boundaries ? We do it the following way: we limit the speedup a sample can have. eg a sample can played at max one octave higher which means twice the speed. Thus the wrap space is given by: wrap_space = audio_card_fragment_size * 2.0 + 3; the audio card fragment size (or jack frames) is constant during the processing so it can be preallocated. of course if you want to increase the fragment size buffers do have to be reallocated but this rarely happens and implementing it is not difficult. the +3 is given by the fact that cubic interpolation fetches the current sample plus 3 subsequent samples. (linear fetches the current plus one subsequent). About memory overhead of the wrap space: it's low since those disk streaming buffers are usually quite big, eg 128k samples, while the audio card's fragmentsize is low compared to that number, eg 512samples. So even if you wanted to play a sample 3 octaves higher (8 times faster), you get 512 * 8 + 3 = 4K samples which is still only 3%. Keep in mind that playing a sample 8 times faster puts quite a big load on the disk streaming system so I guess you would need to increase the above buffer size which would lower the relative memory overhead of the wrap space to below 1% or so. I challenge anyone to come up with a simpler and more efficient approach for streaming samples with varispeed from disk :) Perhaps in ardour's case our approach is not ideal but in the case of LinuxSampler it's the most efficient approach we can think of. cheers, Benno http://www.linuxsampler.org

On Thu, Jun 17, 2004 at 08:22:29PM -0700, Joshua Haberman wrote: Yes, this was discussed here a while back. For all practical platforms that the developers cared about, 32 bit aligned access are atomic. They are not guaranteed to STAY that way, but for now..

On Jun 17, 2004, at 11:25 PM, Tim Hockin wrote: That is orthogonal to the issue that memory barriers address. Even if loads and stores are atomic, that does not guarantee that they happen in program order, as observed by other processors and by I/O devices (such as a sound card). The example in the wikipedia article illustrates the error scenario. I will adapt it here for the case of audio buffers: thread 1: memcpy(ringBufferVector, sourceBuffer, bufferLen); written = 1 thread 2: loop while written != 1 read RingBufferVector If thread 1 and thread 2 are running on different processors in SMP, out of order execution could cause the store "written = 1" to be visible to thread 2 before all of the memcpy stores are. Actually, glancing at the Linux source code it *appears* as though memory barriers are not required on x86. However, they are necessary on ppc; see (http://lxr.linux.no/source/include/asm-ppc/system.h#L17). I don't know about other architectures. Josh

True, but this isn't a reason to choose a ring buffer *over* the multiple buffer approach. The multiple buffer approach is convenient to me for other reasons also. With your scheme, once the GUI thread finally wakes up it will be left with the *oldest* data from the time since it has been asleep. My scheme can give it the *newest* data. How important will this be in practice? I don't know. But at least I will have the option. Not true -- as I described before, I will give the queue an upper limit on the number of buffers it can keep queued. Buffers older than this will be returned to the free pool of buffers. I'm not entirely sure yet, but here are some possibilities. Remember that you're often passing more than just audio data around, you're passing messages between threads. - you definitely need a multiple-reader/multiple-writer stack to implement a buffer freelist. A buffer freelist is a pool of unused buffers, and you want to be able to allocate buffers from and and return buffers to it from any thread. In your case, you may not need a buffer freelist because you're using ring buffers to pass data between threads. - there may be cases where you want both your GUI thread and your disk thread to be able to post messages to the audio thread's message queue. See my reply to Tim. You are not recognizing the danger I am describing. Assuming a sequential execution of loads and stores, what you say is true. However, processors *do not guarantee* that loads and stores are performed in program order! Take the pseudo-assembly: stw sample, 0(ringBuffer) ; copy last sample into the ringbuf stw newptr, 0(write_ptr) ; signal that the write has completed Because modern CPUs allow out-of-order execution of loads and stores (as observed by other CPUs and I/O devices), the processer gives you no guarantee that the first store will be visible to another CPU before the second store is. If your consumer thread is running on another CPU and sees the second store first, it will start reading from the ring buffer before all the stores to that ring buffer have completed! It may be that the chances of this error scenario happening for a RingBuffer are small to none -- after all, your consumer thread won't load the last sample of that buffer until it has performed loads for all the other samples in that buffer, which should give the producer's stores plenty of time to settle. It might be more dangerous if you were transferring smaller amounts of data, like if you were reading and writing one integer at a time. Nevertheless, it's something you should at least be aware of when you are writing lock-free code. See (http://citeseer.ist.psu.edu/adve95shared.html) for a general introduction to issues of shared memory consistency (which is what memory barriers address). Josh