faster way to implement a circular buffer

Hi,

Is there a faster way to implement a circular buffer
on ADSP-21364?

Right now it's implemented like this (but it's slooooooooow):

% Write sample block to cyclic buffer
for (i=0;i<16;i++)
{
    CyclicBuffer[CyclicCounter]=SampleBlock[i];

   CyclicCounter++;
   CyclicCounter=CyclicCounter%256;
}

% Read cyclic buffer
for (i=0;i<256;i++)
{
    Buffer[i]=CyclicBuffer[CyclicCounter];

   CyclicCounter++;
   CyclicCounter=CyclicCounter%256;
}


I see in the documentation that there is a way to setup
circular buffers, but I don't understand how it should
be done, so if somebody out there could list some fast
source code which does the same as the above implementation
I would really be grateful.

Thanks :o)

Hans S=F8rensen wrote:
>
> Is there a faster way to implement a circular buffer
> on ADSP-21364?

the best way to do it is to use the base register (bn) and length
registers (ln) of the chip.  not sure how to do this anymore in C with
the SHArC, but i'll bet Al knows.

> Right now it's implemented like this (but it's slooooooooow):

that's because "%" is often as slow as "/".

> % Write sample block to cyclic buffer
> for (i=3D0;i<16;i++)
> {
>     CyclicBuffer[CyclicCounter]=3DSampleBlock[i];
>
>    CyclicCounter++;
>    CyclicCounter=3DCyclicCounter%256;
> }

i'm glad to see you doing sample block processing.

in general, for C, the faster way is to mask:

    CyclicCounter++;
    CyclicCounter=3DCyclicCounter&0xFF;

and that requires the buffer length to be a power of two.  but it's a
helluva lot faster than division to get the remander.

>
> % Read cyclic buffer
> for (i=3D0;i<256;i++)
> {
>     Buffer[i]=3DCyclicBuffer[CyclicCounter];
>
>    CyclicCounter++;
>    CyclicCounter=3DCyclicCounter%256;
> }
>
>
> I see in the documentation that there is a way to setup
> circular buffers, but I don't understand how it should
> be done, so if somebody out there could list some fast
> source code which does the same as the above implementation
> I would really be grateful.

probably it shows you how to identify and use particular DSP registers
for register variables in C.  it's, of course, an extension of the C
language for the SHArC.

r b-j

robert bristow-johnson said the following on 02/09/2006 15:46:
> 
> Hans S�rensen wrote:
> 
>> Right now it's implemented like this (but it's slooooooooow):
> 
> that's because "%" is often as slow as "/".
> 
>>    CyclicCounter=CyclicCounter%256;
...
> in general, for C, the faster way is to mask:
> 
>     CyclicCounter=CyclicCounter&0xFF;

Wouldn't a decent compiler perform this sort of optimisation 
automatically?  (Just as it might optimise x/2 to x>>1, etc.).

-- 
Oli

Hans S=F8rensen wrote:

> Hi,
>
> Is there a faster way to implement a circular buffer
> on ADSP-21364?

Have a look here for FIR filtering examples on the ADSP-2136x:

http://www.analog.com/processors/sharc/technicalLibrary/codeExamples/2136x_=
simd_code.html

Regards,
Andor

Oli Filth wrote:

> robert bristow-johnson said the following on 02/09/2006 15:46:
> >
> > Hans S=F8rensen wrote:
> >
> >> Right now it's implemented like this (but it's slooooooooow):
> >
> > that's because "%" is often as slow as "/".
> >
> >>    CyclicCounter=3DCyclicCounter%256;
> ...
> > in general, for C, the faster way is to mask:
> >
> >     CyclicCounter=3DCyclicCounter&0xFF;
>
> Wouldn't a decent compiler perform this sort of optimisation
> automatically?  (Just as it might optimise x/2 to x>>1, etc.).

This reminds me of the Star Trek movie where they end up in the present
time to save the future. Scotty goes to a foundary and wants to show
the guys there how to make a new alloy (extra-strength and
transparent). The technician agrees and leads him to their computer.
Scotty picks up the mouse and says: "Hello, computer?"

Andor said the following on 02/09/2006 17:33:
> Oli Filth wrote:
> 
>> robert bristow-johnson said the following on 02/09/2006 15:46:
>>> Hans S�rensen wrote:
>>>
>>>> Right now it's implemented like this (but it's slooooooooow):
>>> that's because "%" is often as slow as "/".
>>>
>>>>    CyclicCounter=CyclicCounter%256;
>> ...
>>> in general, for C, the faster way is to mask:
>>>
>>>     CyclicCounter=CyclicCounter&0xFF;
>> Wouldn't a decent compiler perform this sort of optimisation
>> automatically?  (Just as it might optimise x/2 to x>>1, etc.).
> 
> This reminds me of the Star Trek movie where they end up in the present
> time to save the future. Scotty goes to a foundary and wants to show
> the guys there how to make a new alloy (extra-strength and
> transparent). The technician agrees and leads him to their computer.
> Scotty picks up the mouse and says: "Hello, computer?"

I'm not sure I understand the connection?


-- 
Oli

Oli Filth wrote:

> Andor said the following on 02/09/2006 17:33:
> > Oli Filth wrote:
> >
> >> robert bristow-johnson said the following on 02/09/2006 15:46:
> >>> Hans S=F8rensen wrote:
> >>>
> >>>> Right now it's implemented like this (but it's slooooooooow):
> >>> that's because "%" is often as slow as "/".
> >>>
> >>>>    CyclicCounter=3DCyclicCounter%256;
> >> ...
> >>> in general, for C, the faster way is to mask:
> >>>
> >>>     CyclicCounter=3DCyclicCounter&0xFF;
> >> Wouldn't a decent compiler perform this sort of optimisation
> >> automatically?  (Just as it might optimise x/2 to x>>1, etc.).
> >
> > This reminds me of the Star Trek movie where they end up in the present
> > time to save the future. Scotty goes to a foundary and wants to show
> > the guys there how to make a new alloy (extra-strength and
> > transparent). The technician agrees and leads him to their computer.
> > Scotty picks up the mouse and says: "Hello, computer?"
>
> I'm not sure I understand the connection?

"Hello, computer! Can you just quickly run this FIR filter for me
please?"

:-)

Andor said the following on 02/09/2006 17:49:
> Oli Filth wrote:
> 
>> Andor said the following on 02/09/2006 17:33:
>>> Oli Filth wrote:
>>>
>>>> robert bristow-johnson said the following on 02/09/2006 15:46:
>>>>> Hans S�rensen wrote:
>>>>>
>>>>>> Right now it's implemented like this (but it's slooooooooow):
>>>>> that's because "%" is often as slow as "/".
>>>>>
>>>>>>    CyclicCounter=CyclicCounter%256;
>>>> ...
>>>>> in general, for C, the faster way is to mask:
>>>>>
>>>>>     CyclicCounter=CyclicCounter&0xFF;
>>>> Wouldn't a decent compiler perform this sort of optimisation
>>>> automatically?  (Just as it might optimise x/2 to x>>1, etc.).
>>> This reminds me of the Star Trek movie where they end up in the present
>>> time to save the future. Scotty goes to a foundary and wants to show
>>> the guys there how to make a new alloy (extra-strength and
>>> transparent). The technician agrees and leads him to their computer.
>>> Scotty picks up the mouse and says: "Hello, computer?"
>> I'm not sure I understand the connection?
> 
> "Hello, computer! Can you just quickly run this FIR filter for me
> please?"

Your implication being that compilers aren't clever enough to do this 
sort of optimisation?


-- 
Oli

Oli Filth wrote:

> Andor said the following on 02/09/2006 17:49:
> > Oli Filth wrote:
> >
> >> Andor said the following on 02/09/2006 17:33:
> >>> Oli Filth wrote:
> >>>
> >>>> robert bristow-johnson said the following on 02/09/2006 15:46:
> >>>>> Hans S=F8rensen wrote:
> >>>>>
> >>>>>> Right now it's implemented like this (but it's slooooooooow):
> >>>>> that's because "%" is often as slow as "/".
> >>>>>
> >>>>>>    CyclicCounter=3DCyclicCounter%256;
> >>>> ...
> >>>>> in general, for C, the faster way is to mask:
> >>>>>
> >>>>>     CyclicCounter=3DCyclicCounter&0xFF;
> >>>> Wouldn't a decent compiler perform this sort of optimisation
> >>>> automatically?  (Just as it might optimise x/2 to x>>1, etc.).
> >>> This reminds me of the Star Trek movie where they end up in the prese=
nt
> >>> time to save the future. Scotty goes to a foundary and wants to show
> >>> the guys there how to make a new alloy (extra-strength and
> >>> transparent). The technician agrees and leads him to their computer.
> >>> Scotty picks up the mouse and says: "Hello, computer?"
> >> I'm not sure I understand the connection?
> >
> > "Hello, computer! Can you just quickly run this FIR filter for me
> > please?"
>
> Your implication being that compilers aren't clever enough to do this
> sort of optimisation?

Hello Oli,

au contraire, in fact I know that there is a C compiler that encodes
single line FIR loops for SHARCs (and that takes more than to just
recognize circular buffer usage). I didn't mean to imply anything - the
scene with Scotty just popped up in my head while I skimmed this
thread. Being a humerous (to me) association, I thought it was worth a
post. I'm sorry if it upset you.

Best Regards,
Andor

Andor said the following on 02/09/2006 18:40:
> Oli Filth wrote:
> 
>> Andor said the following on 02/09/2006 17:49:
>>> Oli Filth wrote:
>>>
>>>> Andor said the following on 02/09/2006 17:33:
>>>>> Oli Filth wrote:
>>>>>
>>>>>> robert bristow-johnson said the following on 02/09/2006 15:46:
>>>>>>> Hans S�rensen wrote:
>>>>>>>
>>>>>>>> Right now it's implemented like this (but it's slooooooooow):
>>>>>>> that's because "%" is often as slow as "/".
>>>>>>>
>>>>>>>>    CyclicCounter=CyclicCounter%256;
>>>>>> ...
>>>>>>> in general, for C, the faster way is to mask:
>>>>>>>
>>>>>>>     CyclicCounter=CyclicCounter&0xFF;
>>>>>> Wouldn't a decent compiler perform this sort of optimisation
>>>>>> automatically?  (Just as it might optimise x/2 to x>>1, etc.).
>>>>> This reminds me of the Star Trek movie where they end up in the present
>>>>> time to save the future. Scotty goes to a foundary and wants to show
>>>>> the guys there how to make a new alloy (extra-strength and
>>>>> transparent). The technician agrees and leads him to their computer.
>>>>> Scotty picks up the mouse and says: "Hello, computer?"
>>>> I'm not sure I understand the connection?
>>> "Hello, computer! Can you just quickly run this FIR filter for me
>>> please?"
>> Your implication being that compilers aren't clever enough to do this
>> sort of optimisation?
> 
> Hello Oli,
> 
> au contraire, in fact I know that there is a C compiler that encodes
> single line FIR loops for SHARCs (and that takes more than to just
> recognize circular buffer usage). I didn't mean to imply anything - the
> scene with Scotty just popped up in my head while I skimmed this
> thread. Being a humerous (to me) association, I thought it was worth a
> post. I'm sorry if it upset you.

Not upset, just confused! (Not least because I've never seen Star Trek...)




-- 
Oli