in article mo5%d.37310$6g7.6923@bignews1.bellsouth.net, John E. Hadstate at jh113355@hotmail.com wrote on 03/19/2005 21:46:> > "Sander Vesik" <sander@haldjas.folklore.ee> wrote in message > news:1111285850.795596@haldjas.folklore.ee... >> >> Are these actually more efficent - and that includes the explicit and >> for update - any more efficent in practice than coding it all with a >> mod operation in C and having the compiler do the conversion? Compilers >> have been converting n % m into various non-division invlving operation >> for constant / known m for many decades...it's hard for me to believe that, excepting for some special modulo hardware, that any non-power of two modulo operation using % is quicker than masking for a power of 2 with & (power_of_2 - 1). there is a lot about computer science algorithms i know nothing about.> > while (empty != fill) > { > <do stuff here using empty> > > if (++empty >= RINGBUFSIZE) empty = 0; > } > > The generated code will require far fewer machine cycles > than anything involving modulo computations.while i agree with what is stated, one thing that needs to be said is that there may be many references to data that is not stored exactly to where "empty" is pointing, but at a set of constant (or maybe not constant, for a time-variant algorithm) offsets from "empty". all of those addresses need to have the modulo operation (however it is done) applied to them also, unless you do some kinda trick like Mark's or Stef's. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Online · Live + on demand
February 9-11, 2027
Price goes up Nov 1: register now to lock in today's rate
Register Now →
circular buffering C code
Started by ●March 16, 2005
Reply by ●March 19, 20052005-03-19
Reply by ●March 20, 20052005-03-20
Sander Vesik wrote:> bhooshaniyer <bhooshaniyer@gmail.com> wrote: > >>If I may ask, why code Circular buffer in C at all? Assuming you are using >>a DSP chip for your programming, there is bound to be a hardware circular >>buffer which can be programmed only through assembly.From your question I >>infer that you are worried about cycles and if you are then you shd be >>choosing to code in assembly.Thats your best bet. In fact strictly >>speaking circula buffer is precisely one of the reasons for you to choose >>assembly over C. > > > But doesn't this assume a lot of things as to what he will be keeping > in the buffer?I don't see how data type and pointer management are connected. Can you explain? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 20, 20052005-03-20
"robert bristow-johnson" <rbj@audioimagination.com> wrote in message news:BE625E2E.5687%rbj@audioimagination.com...> in article mo5%d.37310$6g7.6923@bignews1.bellsouth.net,John E. Hadstate at> jh113355@hotmail.com wrote on 03/19/2005 21:46: > > > > > "Sander Vesik" <sander@haldjas.folklore.ee> wrote inmessage> > news:1111285850.795596@haldjas.folklore.ee... > >> > >> Are these actually more efficent - and that includesthe explicit and> >> for update - any more efficent in practice than codingit all with a> >> mod operation in C and having the compiler do theconversion? Compilers> >> have been converting n % m into various non-divisioninvlving operation> >> for constant / known m for many decades... > > it's hard for me to believe that, excepting for somespecial modulo> hardware, that any non-power of two modulo operation using% is quicker than> masking for a power of 2 with & (power_of_2 - 1). thereis a lot about> computer science algorithms i know nothing about.As in: #define RINGBUFSIZE 512*1024 #define RINGBUFMASK (RINGBUFSIZE-1) while (empty != fill) { <do stuff here using empty (as an index)> empty = (empty + 1) & RINGBUFMASK; } which is more efficient than the example below because pipelined processors won't stall on the conditional branch generated by the if(). However, your ring buffer size must be a power of two.> > > > > while (empty != fill) > > { > > <do stuff here using empty> > > > > if (++empty >= RINGBUFSIZE) empty = 0; > > } > > > > The generated code will require far fewer machine cycles > > than anything involving modulo computations. > > while i agree with what is stated, one thing that needs tobe said is that> there may be many references to data that is not storedexactly to where> "empty" is pointing, but at a set of constant (or maybenot constant, for a> time-variant algorithm) offsets from "empty". all ofthose addresses need> to have the modulo operation (however it is done) appliedto them also,> unless you do some kinda trick like Mark's or Stef's. >Having just joined this thread, I've lost Mark's and Stef's remarks, but I can promise you that references to data "that is not stored exactly to where 'empty' is pointing" is not a problem. I am not sure where you see the ghosts, but my feeling is that you are bothered by one of three possible problems: (Problem 1): "empty" and "fill" are pointers (rather than zero-based index variables). That's just dumb programming. The only way the above code works unconditionally is when "empty" and "fill" are zero-based index variables, offsets from some static (or dynamic) base address. C supports arrays of structures. If you don't like the code your compiler generates when accessing arrays of structures, then use multiple primitive arrays. If you have to allocate your arrays dynamically, C provides nice features for supporting base+index addressing (such as the fact that the index works in units of the size of the object to which "base" points). Just typedef a structure and coerce the pointer returned by malloc() to be a "pointer to structure". The compiler will keep track of the size of the structure elements and do the proper address arithmetic. It's probably more efficient to malloc several arrays of primitive types (char, short, long, etc) so the address arithmetic is simplified. (Problem 2): "empty" is an index pointing to some data type that is not processed indivisibly by the machine (e.g.: an 8-byte double on a 16-bit CPU). The potential problem would be changing part of the 8-byte double while the reader was in the process of fetching part of it. This can't happen if the writer and reader follow the necessary ring buffer protocol: the location(s) indexed by "fill" belong to the writer and everything else belongs to the reader. The writer must not increment the "fill" index if doing so would make it equal to the current "empty" index (he's overrunning the reader). The writer must not update the "fill" index until he has completely updated all the data addressed by the "fill" index. When the writer changes "fill", he signals that he has given-up ownership of that set of locations (and taken possession of the next set of locations). (Problem 3): Reader gets slowed down to the point where, if writer increments "fill", he will step on a cell that reader hasn't finished processing. Well, at this point, you have a basic design problem and it's time to go back to the drawing board. Here's a short list of possible choices (there are others, no doubt): a: Use a faster CPU (but don't increase the fill rate). b: Reduce the amount of work being done by the reader (partition the processing and defer some of it or move it to another CPU). c: Use a bigger ring buffer (on the assumption that the average reader throughput is greater than the average writer throughput). d: Force the writer to wait (loop) until the reader gives up the last location. This may involve dropping samples, something that tends to make DSP systems (and their users) gag.
Reply by ●March 20, 20052005-03-20
Hello, My comments inlined. -- ------------------------------ Jaime Andr�s Aranguren Cardona jaac@sanjaac.com SanJaaC Electronics Soluciones en DSP www.sanjaac.com "JS" <jshima@timing.com> escribi� en el mensaje news:1111100844.376234.247750@z14g2000cwz.googlegroups.com...> Hey Robert, > > Can you expound on how the Sharc C compiler supports circular > buffering? I am stuck right now using TI's Code Composter, and as far > as I can tell it doesnt support C-like circular buffering (no bigFrom the VisualDSP++ 3.5 C/C++ Compiler and Library Manual for SHARC DSPs: ------ Circular Buffer Built-In Functions The C/C++ compiler provides the following two built-in functions for using the SHARC circular buffer mechanisms. Circular Buffer Increment of an Index The following operation performs a circular buffer increment of an index. int circindex(int index, int incr, int num_items) The equivalent operation is: index +=incr; if (index <0)index +=nitems; else if (index >=nitems)index -=nitems; Circular Buffer Increment of a Pointer The following operation provides a circular buffer increment of an pointer. int circptr(void * ptr, size_t incr, void * base, size_t buflen) The equivalent operation is: ptr +=incr; if (ptr <base)ptr +=buflen; else if (ptr >=(base+buflen))ptr -=buflen; The compiler also attempts to generate circular buffer increments for modulus array references, such as array[ index %nitems ]. For this to happen, the compiler must be able to determine that the starting value for index will be within the range 0...(nitems-1). When the "-force-circbuf" switch (see on page 1-30) is specified, the compiler will always treat array references of the form [ i%n ] as a circular buffer operation on the array. ------ So, as you can see, it is possible to use circular buffering in C with the SHARC compiler, without problems at all. And you can ALWAYS EASILY hand optimize your code with assembly programming, which is extremely easy to do with the SHARCs. You have far more choices than just relying on the software tools to get the job done.> surprise, eh?). Plus I am trying to show the higher up folks here > that the Sharc is a better way to go than the TI floating pt POS.Besides the good tools, do you have any better argument than the SHARC roadmap for floating point processors? Have a look at this: http://www.analog.com/processors/processors/sharc/index.html And yes: I have a better argument. If floating point perfomance is the main issue, you can always switch to TigerSHARC. have a look at this: http://www.analog.com/processors/processors/tigersharc/index.html and this: http://www.bdti.com/bdtimark/chip_float_scores.pdf As you can see, SHARC/TigerSHARC are the BEST packaged DSP currently available for floating point processing. And will be so for a long time! And this is said by trusted, independent, serious people at BDTI (Berkeley Design Technologies), it is not marketing from ADI!! So SHARC/TigerSHARC is THE processor of choice for signal processing. Aren't you convinced yet? Regards.
