Skip to contentSkip to conversation

a simple FIFO implementation

RFC Peter Chubb 4 participants 4 messages Sep 17, 2004 1 message not in the archive

lore
Share & tools
lore
#1 lore raw
In reply to a message not in the archive
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"Andrew" == Andrew Morton <[email protected]> writes:

Andrew> All the struct needs is head', tail' and Andrew> `number_of_bytes_at_buf', all unsigned.

Andrew> add(char c) {
Andrew> p-> buf[p->head++ % p->number_of_bytes_at_buf] = c;
Andrew> }

This depends on how expensive % is. On IA64, something like this:

     add(char c) {
	     int i = p->head == p->len ? p->head++ : 0;
	     p->buf[i] = c;
     }

is cheaper, as % generates a subroutine call to __modsi3. It also is shorter =-- 12 bundles as opposed to 15.

Signature · 2 lines
Dr Peter Chubb  http://www.gelato.unsw.edu.au  peterc AT gelato.unsw.edu.au
The technical we do immediately,  the political takes *forever*
#2 lore raw
Quoted 9 lines · Peter Chubb

This depends on how expensive % is. On IA64, something like this:

     add(char c) {
	     int i = p->head == p->len ? p->head++ : 0;
	     p->buf[i] = c;
     }

is cheaper, as % generates a subroutine call to __modsi3. It also is shorter =-- 12 bundles as opposed to 15.

I did a similar test once for ppc that found that an increment followed by a test (marked unlikely) was actually quicker in practice than modulo arithmetic.
The branch predictor got it right most of the time, so the test was almost free.

Chris

#4 lore raw
In reply to Peter Chubb
Quoted 9 lines · Peter Chubb

Andrew> All the struct needs is head', tail' and Andrew> `number_of_bytes_at_buf', all unsigned.

Andrew> add(char c) {
Andrew> p-> buf[p->head++ % p->number_of_bytes_at_buf] = c;
Andrew> }

This depends on how expensive % is. On IA64, something like this:

Quoted 7 lines
     add(char c) {
	     int i = p->head == p->len ? p->head++ : 0;
	     p->buf[i] = c;
     }

is cheaper, as % generates a subroutine call to __modsi3. It also is shorter =-- 12 bundles as opposed to 15.

Yup, but this is when doing char-by-char operations.

When using one or two memcpy() we have only two '%' intead of (perhaps) many 'if's.

Of course the memcpy() has its own while() loop but since it's optimized in assembly (and I guess we're not going to implement kfifo_get/put in assembly) I will stay with the memcpy + '%' version.

Stelian.

Signature · 1 line
Stelian Pop <[email protected]>    
#3 lore raw
In reply to Chris Friesen
Quoted 5 lines

I did a similar test once for ppc that found that an increment followed by a test (marked unlikely) was actually quicker in practice than modulo arithmetic. The branch predictor got it right most of the time, so the
test was almost free.

Yep x % y where y isnt constant could result in a divide which will blow away 60+ cycles on some ppc machines. You can do a whole lot in those 60 cycles. Many memcpys for example :)

We removed all modulo arithmetic in the e1000 driver (replaced it with if (x > y) x = 0) and managed to measure an improvement.

Anton