Bruce Momjian wrote:
Is there a TODO here?
I'm just evaluating the performances
of two version the one proposed by
Neil and the one in a "stl::list" fashion.
Tom suggested also to see if is the
case to implement the function size()
constant time or not.
Regards
Gaetano Mendola.
--
Bruce Momjian <[EMAIL PROTECTED]> writes:
> Is there a TODO here?
I've been short on time recently, so I haven't had a chance to make
the suggested changes to the List patch. I'll send in an updated
version of the List changes, and if there aren't any gripes, I'll
begin making the changes to the L
Is there a TODO here?
---
Neil Conway wrote:
> Tom Lane <[EMAIL PROTECTED]> writes:
> > This does suggest that it might be worth making the struct layout be
> >
> > int NodeTag;
> > int length;
> > foo *head;
> >
Neil Conway <[EMAIL PROTECTED]> writes:
> Interesting. I've heard in some shops it is standard policy to order
> the fields in all structs by their descending sizes (making allowances
> for platform-specific variations), so as to reduce padding. Do you
> think it would be worthwhile to systematical
Tom Lane wrote:
Gaetano Mendola <[EMAIL PROTECTED]> writes:
[ use list with master node and circular linking ]
now is very late here ( 04:17 AM ) so I wrote
the wrong code ( not checked ) but show the idea of
avoid "if".
This saves an "if" during addition of a list item, at the cost of
greate
Tom Lane wrote:
Gaetano Mendola <[EMAIL PROTECTED]> writes:
[ use list with master node and circular linking ]
now is very late here ( 04:17 AM ) so I wrote
the wrong code ( not checked ) but show the idea of
avoid "if".
This saves an "if" during addition of a list item, at the cost of
greate
Tom Lane <[EMAIL PROTECTED]> writes:
> This does suggest that it might be worth making the struct layout be
>
> int NodeTag;
> int length;
> foo *head;
> foo *tail;
>
> since this would avoid some padding overhead on a machine where pointers
> are 8 bytes and need 8-byte ali
Neil Conway <[EMAIL PROTECTED]> writes:
> (2) An additional word per List is hardly a prohibitive amount of
> overhead, as we don't create an obscene number of Lists (saving a
> word per ListCell would be a different matter).
Actually, it's free, considering that the alternatives are
Gaetano Mendola <[EMAIL PROTECTED]> writes:
> [ use list with master node and circular linking ]
> now is very late here ( 04:17 AM ) so I wrote
> the wrong code ( not checked ) but show the idea of
> avoid "if".
This saves an "if" during addition of a list item, at the cost of
greater expense du
Gaetano Mendola <[EMAIL PROTECTED]> writes:
> An interesting think that stl::list do is to never do
> an "if" branch during an insert/remove phase
Why is this significant? Surely you're not claiming that avoid the
branch will affect performance in a meaningful way...
> What if you will never call
Neil Conway wrote:
Gaetano Mendola <[EMAIL PROTECTED]> writes:
Why instead of reinvent the whell not use, or at least do a "C" port of
stl::list ?
Because (a) implementing a linked list is pretty trivial (b) the only
difficult part is getting the semantics / API right. I don't see how
std::list
Gaetano Mendola <[EMAIL PROTECTED]> writes:
> Why instead of reinvent the whell not use, or at least do a "C" port of
> stl::list ?
Because (a) implementing a linked list is pretty trivial (b) the only
difficult part is getting the semantics / API right. I don't see how
std::list would help with (
Neil Conway wrote:
Ok, I've attached new versions of list.c and pg_list.h -- this is just a
*rough sketch* of the new List code -- it definitely won't compile, the
intent is just to concretely specify the new List design. Also, I've
only updated the important list functions: I stopped at nth().
(I'
I said:
> No, lfirst and friends will need to apply to ListCells not to Lists,
> else the coding of foreach loops will break everywhere. I think there
> are many more places that will want lfirst to apply to a ListCell than
> will want it to apply to a raw List.
On the other hand, we will need to
Neil Conway <[EMAIL PROTECTED]> writes:
> #define length(l) ((l)->length)
> #define value(cell) ((cell)->elem.ptr_value)
> #define ivalue(cell) ((cell)->elem.int_value)
> #define ovalue(cell) ((cell)->elem.oid_value)
Couple of objections here
Ok, I've attached new versions of list.c and pg_list.h -- this is just a
*rough sketch* of the new List code -- it definitely won't compile, the
intent is just to concretely specify the new List design. Also, I've
only updated the important list functions: I stopped at nth().
(I've attached the wh
Neil Conway <[EMAIL PROTECTED]> writes:
> On Mon, 2003-11-03 at 18:19, Tom Lane wrote:
>> I have already done something much like this in a few hotspots using the
>> FastList structure. But notationally, it's a pain in the neck compared
>> to the existing List code. If you can think of a way to i
On Mon, 2003-11-03 at 18:19, Tom Lane wrote:
> Hard to tell. Since I haven't seen any evidence that equal() on lists
> is a particular hotspot, I'd lean against adding complexity and
> maintenance burden here.
Ok, I agree -- probably not worth doing, then.
> I have already done something much li
Neil Conway <[EMAIL PROTECTED]> writes:
> Do you think it would be worth the trouble to use both algorithms, and
> then test on the node tag of the first element to decide which one to
> use? (The assumption being lists are homogeneous).
Hard to tell. Since I haven't seen any evidence that equal(
On Mon, 2003-11-03 at 16:39, Tom Lane wrote:
> The point is that the elements of the lists could be large, complicated
> structures that will take noticeable amounts of time to compare.
Good point, I agree with your analysis. At the very least, I'll add a
comment to equal() explaining why the algo
Neil Conway <[EMAIL PROTECTED]> writes:
> On Mon, 2003-11-03 at 10:04, Tom Lane wrote:
>> You have effectively reverted the code to its previous slow state.
> Erm, the original version of this code in CVS (from ~7 years ago) is the
> following:
Hm. I coulda sworn that at some point I changed tha
On Mon, 2003-11-03 at 10:04, Tom Lane wrote:
> You have effectively reverted the code to its previous slow state.
Erm, the original version of this code in CVS (from ~7 years ago) is the
following:
case T_List:
{
List *la = (List*)a;
List *lb = (List*)b;
Neil Conway <[EMAIL PROTECTED]> writes:
> This code is inefficient, however: length() requires iterating through
> the entire list, so this code scans both lists twice. The attached patch
> improves this by implementing equal() with a single scan of both lists.
You have effectively reverted the co
Currently, equal() does the following for List nodes:
case T_List:
{
List *la = (List *) a;
List *lb = (List *) b;
List *l;
/*
* Try to reject by length check before we grovel through
* all the elements...
*/
if
24 matches
Mail list logo
