On 05/24/2010 01:49 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 12:27:10 -0400, Andrei Alexandrescu
<[email protected]> wrote:
A pointer to the end element would be required for both appending and
back().
This further erodes my confidence. Size needs to be maintained _and_ a
pointer to the last element must be maintained. For many uses, all of
this stuff is unnecessary overhead.
You make it sound like incrementing a counter and changing a pointer are
incredibly slow operations :)
They are. Ask Walter for a good example.
The overhead of storage is minimal
compared to the elements of the list, which do not contain said overhead.
I'm talking containers of lists here.
I think we need to build the shared vision that in Phobos we're
competing against hand-written, highly-optimized code. This is the
fight STL took and largely won. We can't afford to lower our standards
for one tiny bit.
I was once talking over a beer about the advantages of container
abstractions. Walter slapped my face by defining the fastest SLL in
the world on a napkin. It looked like this:
struct List { int v; List * next; }
He took so little time to define that, and the primitives he needed
were so simple and fast, that it was an absolute overkill to replace
that with a generic whiz-bang container. If I'd mentioned there'd be
any extra data involved, that would mean the end of negotiation. "Why
do you need that?" "For length()!" "But I don't need length()!" "Well
you have to." "That's Communism in design!"
And I agree.
But something like the above is prone to all sorts of nasty things, like
inadvertent cycles in your list.
Yeah, and I'd have my list of arguments to add too.
Which may be acceptable to you if you
want the bleeding fastest speed available. There will always be tailored
code crafted to be as fast as possible for some specific design and
dcollections and your slist just won't fit the bill.
Except that the set is considerably smaller for a well-designed slist.
And dcollections' link list node is exactly what you wrote there (with a
prev pointer of course). The only difference is, I don't define an
element is the same as a list. The whole list has it's own data,
including a pointer to the first element in the list.
Look at D's arrays. Is appending with D's arrays the fastest it possibly
could be? Hell no, but it's good enough for most situations, and safe.
If I could make them faster without adversely affecting the performance
of other operations, I would. There's considerable constraints at plain
in the array design for historical and other reasons.
Andrei
