> On 14 Apr 2015, at 2:09 , Marcus Denker <marcus.den...@inria.fr> wrote: > > >> On 14 Apr 2015, at 14:00, Sven Van Caekenberghe <s...@stfx.eu> wrote: >> >> Peter, >> >>> On 14 Apr 2015, at 13:52, Peter Uhnák <i.uh...@gmail.com> wrote: >>> >>> I was surprised to learn that DoubleLinkedList is descendant of Object, >>> while LinkedList is descendant of SequencableCollection. Is there a >>> particular reason behind this? Are they really so conceptually different >>> that DLL is not even considered a collection? >>> >>> Thanks, >>> Peter >> >> DoubleLinkedList was added to help the implementation of [LRU|TTL]Cache. It >> was kept small and independent. >> >> Inheriting from [Sequenceable]Collection is a larger responsibility, entails >> more requirements. >> >> I would not be against this, although I am not 100% sure it is easy (some >> methods return the link nodes, not the elements, a distinction unknown to >> collections in general - LinkedList is a bit ugly in this respect too). In >> any case, it would have to be supported by enough tests. It could be a nice >> project for Pharo 5. > > One problem with LinkedList is that it is used by the scheduler and carefully > written to be intererrupt-check free in some (undocumented) cases… in the past > this has already lead to very bad side-effects when people wanted to improve > it or change it. > > Marcus
IIRC, #removeLink:ifAbsent: is the only method (... that we've noticed) that needs to be atomic for the scheduler to work.(in other words, it can end up trying to remove the same process from different threads at the same time) The change was made during a sprint to allow adding arbitrary objects and create links on the fly (inspired by Ruby, or so I was told), in the process the old remove:ifAbsent: turned into removeLink:ifAbsent, and a suspension point was introduced in the process, which meant, once in a blue moon, the scheduler would get stuck trying to remove a process that had already been removed. In other words; it's not a pleasant class to change. WRT being a subclass of SequenceableCollection; while technically true, that API is much wider than what you'd expect from a classic link list, and the inherited implementations mostly assume O(1) #at: performance. Very little is reimplemented, so most of it is rather slow if you try to actually use any of it: ll := LinkedList withAll:#(a b c d e f g h i j k l m n o p q r s t u v x y z). [ll allButFirst: 15] bench '150,365 per second' aa := Array withAll: #(a b c d e f g h i j k l m n o p q r s t u v x y z). [aa allButFirst: 15] bench 10,055,029 per second Aside from pure bugs, there's also other oddities like the species being Array, but iteration methods reimplemented using self class. IOW: If you are looking for a LinkedList actually worth using, look elsewhere. DoubleLinkedList may not be a Collection, but at least the API is small enough to grasp, and the parts that are there act as you expect them to. Cheers, Henry
