Single Linked List / Performance
Peter Bartal
the code below handles a single list. Moving (sllFifoPos) is
significantly slower than searching (sllFifoFind)... I understand it
could depend on the compiler, hardware etc. But this difference is
quite big so I suspect my sllFindPos is somehow inefficient. What am I
doing wrong ?
Thanks,
Peter
mailto:bar...@gmx.net
void *sllFifoFind ( psllFifo pHead, void *data, size_t size )
{
psllItem pItem = NULL;
void *found = NULL;
DEBUG ( LOW_LEVEL, "sllFifoFind Start", FALSE );
pItem = pHead->top;
while ( NULL != pItem )
{
if ( 0 == memcmp ( pItem->payload, data, size ) )
{
found = pItem->payload;
break;
}
pItem = pItem->next;
}
DEBUG ( LOW_LEVEL, "sllFifoFind Exit", FALSE );
return ( found );
}
void *sllFifoPos ( psllFifo pHead, int pos )
{
psllItem pItem = NULL;
void *found = NULL;
DEBUG ( LOW_LEVEL, "sllFifoPos Start", FALSE );
pItem = pHead->top;
while ( NULL != pItem )
{
if ( 0 == pos ) break;
pItem = pItem->next;
pos--;
}
if ( NULL != pItem )
{
found = pItem->payload;
}
DEBUG ( LOW_LEVEL, "sllFifoPos Exit", FALSE );
return ( found );
}
Tobias Oed
>
> Hi,
>
> the code below handles a single list. Moving (sllFifoPos) is
> significantly slower than searching (sllFifoFind)... I understand it
> could depend on the compiler, hardware etc. But this difference is
> quite big so I suspect my sllFindPos is somehow inefficient. What am I
> doing wrong ?
>
Hi Peter, netiquette says "post here, read here."
>
> void *sllFifoFind ( psllFifo pHead, void *data, size_t size )
> {
> psllItem pItem = NULL;
> void *found = NULL;
>
> DEBUG ( LOW_LEVEL, "sllFifoFind Start", FALSE );
> pItem = pHead->top;
> while ( NULL != pItem )
> {
> if ( 0 == memcmp ( pItem->payload, data, size ) )
That's the culprit. You compare memory regions, if they are
big that'll be expensive.
> {
> found = pItem->payload;
> break;
> }
> pItem = pItem->next;
> }
> DEBUG ( LOW_LEVEL, "sllFifoFind Exit", FALSE );
> return ( found );
> }
>
> void *sllFifoPos ( psllFifo pHead, int pos )
> {
> psllItem pItem = NULL;
> void *found = NULL;
>
> DEBUG ( LOW_LEVEL, "sllFifoPos Start", FALSE );
> pItem = pHead->top;
> while ( NULL != pItem )
> {
> if ( 0 == pos ) break;
> pItem = pItem->next;
> pos--;
Here you just decrement an int, that's cheap.
This won't speed up things but I don't see your motivation for
the found pointer. Why not use
void *sllFifoFind ( psllFifo pHead, void *data, size_t size )
{
psllItem pItem;
DEBUG ( LOW_LEVEL, "sllFifoFind Start", FALSE );
for ( pItem = pHead->top ; NULL != pItem ; pItem = pItem->next)
{
if ( 0 == memcmp ( pItem->payload, data, size ) )
{
break;
}
}
DEBUG ( LOW_LEVEL, "sllFifoFind Exit", FALSE );
return ( pItem );
}
void *sllFifoPos ( psllFifo pHead, int pos )
{
psllItem pItem;
DEBUG ( LOW_LEVEL, "sllFifoPos Start", FALSE );
pItem = pHead->top;
for ( pItem = pHead->top ; NULL != pItem && pos > 0 ; pItem =
pItem->next,pos--)
;
DEBUG ( LOW_LEVEL, "sllFifoPos Exit", FALSE );
return ( pItem );
}
btw, the for(){} of sllFifoFind could also be empty by && the
condition of the if in the exit condition of the for.
In order to speed up things some you may want to add a (sort of)
hash element to your psllItem struct. (you should have posted the
def of it). Based on the payload, you would init it when adding an
element to the list and compare that to the hash value of what you're
looking for. Then do the memcmp only if the hash values are equal.
Also, at all times you should keep in mind "optimize only when too
slow or doesn't fit" as it says in a regular's sig here.
HTH, Tobias.
CBFalconer
>
> the code below handles a single list. Moving (sllFifoPos) is
> significantly slower than searching (sllFifoFind)... I understand it
> could depend on the compiler, hardware etc. But this difference is
> quite big so I suspect my sllFindPos is somehow inefficient. What am I
> doing wrong ?
>
I see nothing intrinsically wrong, except that memcmp is not going
to be portable unless the structure pointed to is made up of
chars. Otherwise undefined packing will foul it.
In addition, your Find routine finds the first item in the list,
while the Pos routine finds the nth. With multiple equal payload
entries the Find may well be much faster. You need to examine the
data on which the system is working.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Peter Bartal
> btw, the for(){} of sllFifoFind could also be empty by && the
> condition of the if in the exit condition of the for.
>
> In order to speed up things some you may want to add a (sort of)
> hash element to your psllItem struct. (you should have posted the
> def of it). Based on the payload, you would init it when adding an
> element to the list and compare that to the hash value of what you're
> looking for. Then do the memcmp only if the hash values are equal.
> Also, at all times you should keep in mind "optimize only when too
> slow or doesn't fit" as it says in a regular's sig here.
>
> HTH, Tobias.
Hallo,
the motivation for the found pointer is that I have to return the
value of the payload and not the pointer to the found element.
Peter
Peter Bartal
> to be portable unless the structure pointed to is made up of
> chars. Otherwise undefined packing will foul it.
>
> In addition, your Find routine finds the first item in the list,
> while the Pos routine finds the nth. With multiple equal payload
> entries the Find may well be much faster. You need to examine the
> data on which the system is working.
Hi,
I use a set of data which is inserted multiple times into the sll for testing.
I was aware of this but your comment made me look at it closer and
yes it is indeed the reason why is my Find faster than my Pos.
Thanks,
Peter
CBFalconer
>
> > I see nothing intrinsically wrong, except that memcmp is not going
> > to be portable unless the structure pointed to is made up of
> > chars. Otherwise undefined packing will foul it.
> >
> > In addition, your Find routine finds the first item in the list,
> > while the Pos routine finds the nth. With multiple equal payload
> > entries the Find may well be much faster. You need to examine the
> > data on which the system is working.
>
> testing. I was aware of this but your comment made me look at it closer
> and yes it is indeed the reason why is my Find faster than my Pos.
Which is one more reason why all your routines should be clearly
commented at to what the routine does, in general. If you had had
comments such as:
/* Find first occurance ... */
and
/* Find nth item ... */
on your functions, the reason would have been self-evident.
Tobias Oed
Indeed. Also, I misread your original post, I thought that
find was slower that pos. sorry about these brain farts. I
guess Chuck has got better coffee than I.
Tobias.
Peter Bartal
> commented at to what the routine does, in general. If you had had
> comments such as:
>
> /* Find first occurance ... */
>
> and
>
> /* Find nth item ... */
>
> on your functions, the reason would have been self-evident.
Hi,
this is the header of the function:
/*
* Function : sllFifoFind
* Input : pHead - pointer to the header structure of the
used
* FIFO
* args - arguments for the compare function
* *Compare- pointer to the function which will do
the comp
* are. [int MyCompare ( void *x, void *y
)]
* Output : payload - pointer to the data which was found
* Function Calls : None
* Description : Goes through the list SEQUENTIALLY and compares
every one
* member. When the matching item is found the
pointer to
* that item is returned. Very INEFFICIENT for
LARGE lists.
* Of course only the first occurence will be
found.
* Version : 1.0
* Author : Peter Bartal
* Change Log : Ver Date who Description
* 1.0 10.08.2001 pba Created
* 1.1 14.08.2001 pba Compare function
implemented
*/
so the comment was there. Just somehow I screwed up and spent much
time searching elsewhere for the problem that I coudn't see the
obvious. I think I should get my own teddybear with rayban sunglasses
for test strategy discussion ;-) Anyway thanks for the kick in the ass
to wake me up.
Peter
Peter Bartal
> find was slower that pos. sorry about these brain farts. I
> guess Chuck has got better coffee than I.
> Tobias.
Hi,
this is just out of curiosity. I read lot's of code where
people use the 'for' statement even when it's obvious that
the "while" or "do {} while" construct would be suitable. Is
there any particular reason ? (Performance etc) or is it just
the personal preference ? I still miss the pascal construct
'repeat-until'. I mean there is nothing that #define wouldn't
cure but... Anyway I think the readability of the code would
be better.
Peter
Gunnar Andersson
On 14 Aug 2001, Peter Bartal wrote:
> this is just out of curiosity. I read lot's of code where
> people use the 'for' statement even when it's obvious that
> the "while" or "do {} while" construct would be suitable. Is
> there any particular reason ? (Performance etc) or is it just
> the personal preference ? I still miss the pascal construct
> 'repeat-until'. I mean there is nothing that #define wouldn't
> cure but... Anyway I think the readability of the code would
> be better.
Performance is not an issue, you can expect any decent compiler to
generate equivalent code regardless of whether you use for or while.
I think it's pretty much a matter of personal taste. Myself I tend
to use do-while less than the others as it's more informative to
see "while ( <condition> )" than "do {" at the top of a loop when
reading code.
/ Gunnar
Greg Comeau
Peter Bartal <bar...@gmx.net> wrote:
>> Indeed. Also, I misread your original post, I thought that
>> find was slower that pos. sorry about these brain farts. I
>> guess Chuck has got better coffee than I.
>> Tobias.
>
> people use the 'for' statement even when it's obvious that
> the "while" or "do {} while" construct would be suitable. Is
> there any particular reason ? (Performance etc) or is it just
> the personal preference ? I still miss the pascal construct
> 'repeat-until'. I mean there is nothing that #define wouldn't
> cure but... Anyway I think the readability of the code would
> be better.
I think three things compound the issue:
1) Some people never learn all the possible looping construct
2) Some people don't know how to use all the looping constructs
3) Folks just get used to using the for-loop and "get stuck"
by habit into "thinking that way".
--
Greg Comeau Countdown to "export": December 1, 2001
Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
Tasty C99/C++ Combo: Dinkumware libs + Comeau Compilers == WOW!!!
CBFalconer
>
> > Which is one more reason why all your routines should be clearly
> > commented at to what the routine does, in general. If you had had
> > comments such as:
> >
> > /* Find first occurance ... */
> >
> > and
> >
> > /* Find nth item ... */
> >
> > on your functions, the reason would have been self-evident.
>
IMHO your comments are excessive, and lose the pith in the
jungle. Too much also means that they will not be maintained
properly. You may have some ill-conceived company standard
hanging over you, though.
I personally would rather see:
/* ========== unique inter function delimiter ========== */
/* Broad outline of function. Maybe one line for author */
/* This is for the benefit of the caller. Limitations. */
/* Optional list of globals used. */
type fname(type param1, /* any details on param1 */
type param2, /* ditto for param2 */
type .... ) /* ditto .... */
{
type localitem; /* possible comment */
/* the code, with possible implementation explanations */
} /* fname */
The final /* fname */ together with the inter function delim makes
it easy to scan through code later. I would hope the names of
param1, param2, localitem, etc. would make the comments
unnecessary. IFF this is to be externally accessible I would copy
the whole header portion, comments and all, into the .h file.
Thus any user can find out all s/he needs to know from the .h file
alone.
If you want to keep records of changes etc, that is the function
of the code repository.
As I said, this is my personal opinion, and it borders on style
wars.
Of course, if you have people who count lines of code, and assume
that more is better, then ....
Tobias Oed
I use for(){} when there is need for an inititialization a test
and an increment on which the control of the loop depends.
In the case of your code,
pItem = pHead->top;
while ( NULL != pItem )
{
if ( 0 == memcmp ( pItem->payload, data, size ) )
{
found = pItem->payload;
break;
}
pItem = pItem->next;
}
there clearly is an init (pItem=pHead->top) a test NULL!=pItem and
an increment pItem=pItem->next. With your while loop they are in
separate place, with a for loop they are together:
for(pItem=pHead->top ; NULL!=pItem ; pItem=pItem->next){
etc...
}
I use while(){} when there is a test only as in
while((c=fgetc(stdin))!=EOF){etc...}
I use do{}while() much less and only when I need the loop to be
executed once. This one actually sounds like the repeat-until
you're missing (well, repeate-while actually, but a ! isn't
that hard to type after all).
Tobias.
Peter Bartal
Hi,
right, kind of company standard. But trying to evolve it into something
useful.
1) I agree that the params and variables should be selfdescribing if possible
Q) If I want to use the comment header for interface description is it not
appropriate ? (automatically extracted like doc<anything>)
2) /* fname */ this seems reasonable.
Q) How about /* fi */ etc... ? I assume for large loops/ifs which doesn't
fit the screen it would be OK. For small loops/ifs it would just make the
code overcrowded.
3) Change log is hard to maintain when 'mishandled'. But CVS, ClearCase
whatever doesn't give you the possibility to comment on function level.
Rather on source/file level. This could lead to excessive comments for
every source file in repository. On the other hand the change log isn't
updated that much anyway.
4) Lines of code pure - no prob excluding comments with tools/custom scripts
so this is not applicable
Greets,
Peter
Peter Bartal
> and an increment on which the control of the loop depends.
> In the case of your code,
>
> pItem = pHead->top;
> while ( NULL != pItem )
> {
> if ( 0 == memcmp ( pItem->payload, data, size ) )
> {
> found = pItem->payload;
> break;
> }
> pItem = pItem->next;
> }
>
> there clearly is an init (pItem=pHead->top) a test NULL!=pItem and
> an increment pItem=pItem->next. With your while loop they are in
> separate place, with a for loop they are together:
>
> for(pItem=pHead->top ; NULL!=pItem ; pItem=pItem->next){
> etc...
> }
>
> I use while(){} when there is a test only as in
>
> while((c=fgetc(stdin))!=EOF){etc...}
>
> I use do{}while() much less and only when I need the loop to be
> executed once. This one actually sounds like the repeat-until
> you're missing (well, repeate-while actually, but a ! isn't
> that hard to type after all).
> Tobias.
Hallo,
so back to school :-)
1) Use for when you want to loop zero or more times and you have to init
some 'loop' wariables.
2) Use while {} when you loop zero or more times and you don't need to
init any 'loop' variables
3) Use do {} while when you want to loop one or more times.
Anyway we are missing a construct for : "loop one or more times and want
to init 'loop' wariables. This could lead to a new loop contruct:
repeat ( <init variables here>; <any processing here> )
{
<processing statements>;
}
until ( <exit decision> );
This is funny. Not that it would be necessary. But it's funny.
Peter