Digital Mars - digitalmars.D.dtl - more mintl class ideas

↑ ↓ ← → "Ben Hinkle" <ben.hinkle gmail.com> writes:

Well I've started to explode the class and interface list to be more 
standard. The squished hierarchy wasn't wearing very well. I'm also testing 
names without I or C prefixes and using the package to distinguish the 
classes from the structs. Note I'm leaning towards keeping slicing and 
anything that returns collections to be in the class hierarchy instead of 
the interface hierarchy so that covariance will work. That is, if the slice 
of an AbstractList is an AbstractList then the slice of a LinkedList can be 
a LinkedList.

/**  Interface Hierarchy
 *
 *   Enumeration(Value)
 *     IndexedEnumeration(Index,Value)
 *
 *   Container(Value) : Enumeration(Value)
 *     AssocContainer(Key,Value) : IndexedEnumeration(Key,Value)
 *     List(Value) : IndexedEnumeration(size_t,Value)
 *     Set(Value)
 *     MultiSet(Value)
 *     Stack(Value)
 *     Queue(Value)
 */

/**  Class Hierarchy
 *
 *  AbstractContainer(Value) : Container!(Value)
 *    AbstractAA(Key,Value) : AssocContainer(Key,Value)
 *      ConcurrentAA
 *      HashTable
 *      SortedAA
 *      LinkedAA
 *    AbstractList(Value) : List(Value)
 *      LinkedList
 *      ArrayList
 *      Deque
 *      CircularList
 *      SList
 *      CircularSList
 *    AbstractSet(Value) : Set(Value)
 *      HashSet
 *      SortedSet
 *      LinkedSet
 *    AbstractMultiSet(Value) : MultiSet(Value)
 *      HashMultiSet
 *      SortedMultiSet
 *      LinkedMultiSet
 *    AbstractStack(Value) : Stack(Value)
 *      ArrayStack
 *      DequeStack
 *      LinkedStack
 *    AbstractQueue(Value) : Queue(Value)
 *      ArrayQueue
 *      DequeQueue
 *      LinkedQueue
 *      PriorityQueue
 */

May 22 2005

↑ ↓ ← → "Ben Hinkle" <bhinkle mathworks.com> writes:

 Ben, this is really good spec. - I like it. If you need co-developer for
 this project please do not hesitate to contact me.


cool - thanks. Right now I'm shuffling the earlier class code around to fit 
the new structure. I'll try to put something up quickly so that you can take 
some of the load. Once I have some basics would you want to write the 
thread-safe wrappers? I'm picturing something like the helper functions in 
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html

May 24 2005

↑ ↓ ← → Dejan Lekic <leka entropy.tmok.com> writes:

 Ben, this is really good spec. - I like it. If you need co-developer for
 this project please do not hesitate to contact me.


 cool - thanks. Right now I'm shuffling the earlier class code around to
 fit the new structure. I'll try to put something up quickly so that you
 can take some of the load. Once I have some basics would you want to write
 the thread-safe wrappers? I'm picturing something like the helper


My opinion is that MinTL should be _completely_ thread-safe by default.
Reason for this is simple fact that in few years almost all home computers
will most likely have two processors (or two cores) . Even nowadays
processors have some threading features (HT from Intel for example).
So IT population will just be more and more focused on multithreading.

 functions in
 http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collections.html


I'll check this out.

-- 
...........
Dejan Lekic
  http://dejan.lekic.org

May 27 2005

↑ ↓ ← → "Ben Hinkle" <bhinkle mathworks.com> writes:

"Dejan Lekic" <leka entropy.tmok.com> wrote in message 
news:d77epc$1p5d$1 digitaldaemon.com...
 Ben, this is really good spec. - I like it. If you need co-developer for
 this project please do not hesitate to contact me.


 cool - thanks. Right now I'm shuffling the earlier class code around to
 fit the new structure. I'll try to put something up quickly so that you
 can take some of the load. Once I have some basics would you want to 
 write
 the thread-safe wrappers? I'm picturing something like the helper


 My opinion is that MinTL should be _completely_ thread-safe by default.
 Reason for this is simple fact that in few years almost all home computers
 will most likely have two processors (or two cores) . Even nowadays
 processors have some threading features (HT from Intel for example).
 So IT population will just be more and more focused on multithreading.


That's what Sun thought when they first wrote the JDK. Now all the 
thread-safe containers like Vector and Hashtable are deprecated and replaced 
with non-threadsafe versions. One reason is that often just making the 
get/set calls threadsafe isn't the right level of granularity. Typically if 
you traverse a vector or perform some complex operation you want to lock the 
container during the whole loop and not just on every get/set. The other big 
reason Vector isn't used anymore is speed - the non-synchronized version is 
just faster. Thread safety should be required infrequently enough that the 
wrappers don't make the system unmaintainable.

of course YMMV - it all depends on the application.

May 27 2005

↑ ↓ ← → "Kris" <fu bar.com> writes:

FWIW: I think Ben is right on the mark here ~ particularly so regarding the
"granularity" aspect. Thread-safety is an important issue, but insisting
everyone should always pay that "tax" is not necessarily the right answer.


"Ben Hinkle" <bhinkle mathworks.com> wrote in message
news:d77gdf$1qm1$1 digitaldaemon.com...
 "Dejan Lekic" <leka entropy.tmok.com> wrote in message
 news:d77epc$1p5d$1 digitaldaemon.com...
 Ben, this is really good spec. - I like it. If you need co-developer








 this project please do not hesitate to contact me.


 cool - thanks. Right now I'm shuffling the earlier class code around to
 fit the new structure. I'll try to put something up quickly so that you
 can take some of the load. Once I have some basics would you want to
 write
 the thread-safe wrappers? I'm picturing something like the helper


 My opinion is that MinTL should be _completely_ thread-safe by default.
 Reason for this is simple fact that in few years almost all home




 will most likely have two processors (or two cores) . Even nowadays
 processors have some threading features (HT from Intel for example).
 So IT population will just be more and more focused on multithreading.


 That's what Sun thought when they first wrote the JDK. Now all the
 thread-safe containers like Vector and Hashtable are deprecated and


 with non-threadsafe versions. One reason is that often just making the
 get/set calls threadsafe isn't the right level of granularity. Typically


 you traverse a vector or perform some complex operation you want to lock


 container during the whole loop and not just on every get/set. The other


 reason Vector isn't used anymore is speed - the non-synchronized version


 just faster. Thread safety should be required infrequently enough that the
 wrappers don't make the system unmaintainable.

 of course YMMV - it all depends on the application.

May 30 2005

↑ ↓ ← → "Ben Hinkle" <bhinkle mathworks.com> writes:

 why not use version(threadsafe) (or similar) inside MinTL and have simple
 ability to easily have both threadsafe and non-threadsafe MinTL?


Which containers would you like to be threadsafe? There's the whole 
"mintl.concurrent" package for thread-aware containers. It has stacks, 
queues and hashtables. I haven't been doing anything with that package in a 
while so if you have any ideas how to wrap the non-threadsafe versions with 
thread-safe versions please feel free to play around. It could be the way to 
go is to follow the Java model and have thread-safe wrappers for the classes 
and just have all operations synchronize on the container object. Slow, but 
simple. Plus one doesn't have to write a thread-safe version of all the 
types - you just need one wrapper per interface.

May 24 2005

↑ ↓ ← → "Ben Hinkle" <bhinkle mathworks.com> writes:

"Dejan Lekic" <leka entropy.tmok.com> wrote in message 
news:d6vtud$25n6$1 digitaldaemon.com...
 That is precisely why i wrote previous post... I would like  WHOLE MinTL 
 to
 be threadsafe if it is compiled with "threadsafe" version turned on.

 IMHO there is no need for separate package...

 -- 
 ...........
 Dejan Lekic
  http://dejan.lekic.org


The implementation would be verbose, I think. The 'version' statements would 
wind up looking like
version(threadsafe) {
  synchronized bool isEmpty() { return isEmptyImpl(); }
} else {
  bool isEmpty() { return isEmptyImpl(); }
}
final bool isEmptyImpl(){ ... }

and that would have to happen in every container class for every method. 
With the 'wrapper' approach it becomes

 class SyncList(Value) {
    List!(Value) impl;
    synchronized bool isEmpty(){ return impl.isEmpty(); }
}

and you write it just once per interface method. Then any List 
implementation can be made "thread-safe" by wrapping it in a SyncList. Off 
the top of my head I'd prefer the wrapper approach. It also allows 
synchronized and unsynchronized Lists to be used in the same app easily.

May 24 2005

↑ ↓ ← → "Ben Hinkle" <ben.hinkle gmail.com> writes:

"Dejan Lekic" <leka entropy.tmok.com> wrote in message 
news:d715a4$sdd$1 digitaldaemon.com...
 Have You, than, considered having ONLY threadsafe MinTL?
 Personally I am writing more and more code which uses threads, and I am
 pretty sure a lot of other developers do the same...

 -- 
 ...........
 Dejan Lekic
  http://dejan.lekic.org


The "basic" MinTL is not thread-safe. The containers in mintl.concurrent are 
designed to be used in a threaded app so they are very fast. Not every 
container type is in mintl.concurrent so I can see the use case here or 
there where a synchronized wrapper would come in handy.

May 25 2005

↑ ↓ ← → Ben Phillips <Ben_member pathlink.com> writes:

A lot of those ideas sound great, but why DequeQueue and DequeStack? They only
need insertions at one end, so I don't understand the advantages of using a
deque. However, I do like the idea of having Array&Stack versions.

In article <d6ri5c$90$1 digitaldaemon.com>, Ben Hinkle says...
Well I've started to explode the class and interface list to be more 
standard. The squished hierarchy wasn't wearing very well. I'm also testing 
names without I or C prefixes and using the package to distinguish the 
classes from the structs. Note I'm leaning towards keeping slicing and 
anything that returns collections to be in the class hierarchy instead of 
the interface hierarchy so that covariance will work. That is, if the slice 
of an AbstractList is an AbstractList then the slice of a LinkedList can be 
a LinkedList.

/**  Interface Hierarchy
 *
 *   Enumeration(Value)
 *     IndexedEnumeration(Index,Value)
 *
 *   Container(Value) : Enumeration(Value)
 *     AssocContainer(Key,Value) : IndexedEnumeration(Key,Value)
 *     List(Value) : IndexedEnumeration(size_t,Value)
 *     Set(Value)
 *     MultiSet(Value)
 *     Stack(Value)
 *     Queue(Value)
 */

/**  Class Hierarchy
 *
 *  AbstractContainer(Value) : Container!(Value)
 *    AbstractAA(Key,Value) : AssocContainer(Key,Value)
 *      ConcurrentAA
 *      HashTable
 *      SortedAA
 *      LinkedAA
 *    AbstractList(Value) : List(Value)
 *      LinkedList
 *      ArrayList
 *      Deque
 *      CircularList
 *      SList
 *      CircularSList
 *    AbstractSet(Value) : Set(Value)
 *      HashSet
 *      SortedSet
 *      LinkedSet
 *    AbstractMultiSet(Value) : MultiSet(Value)
 *      HashMultiSet
 *      SortedMultiSet
 *      LinkedMultiSet
 *    AbstractStack(Value) : Stack(Value)
 *      ArrayStack
 *      DequeStack
 *      LinkedStack
 *    AbstractQueue(Value) : Queue(Value)
 *      ArrayQueue
 *      DequeQueue
 *      LinkedQueue
 *      PriorityQueue
 */

Aug 24 2005

↑ ↓ ← → Ben Phillips <Ben_member pathlink.com> writes:

Pardon me, I meant I like the idea of Array & Linked list versions of stacks and
queues (not a stack version :P ). Also, how will you implement LinkedSet,
LinkedMultiSet, and LinkedAA?

In article <dei1vq$2vat$1 digitaldaemon.com>, Ben Phillips says...
A lot of those ideas sound great, but why DequeQueue and DequeStack? They only
need insertions at one end, so I don't understand the advantages of using a
deque. However, I do like the idea of having Array&Stack versions.

In article <d6ri5c$90$1 digitaldaemon.com>, Ben Hinkle says...
Well I've started to explode the class and interface list to be more 
standard. The squished hierarchy wasn't wearing very well. I'm also testing 
names without I or C prefixes and using the package to distinguish the 
classes from the structs. Note I'm leaning towards keeping slicing and 
anything that returns collections to be in the class hierarchy instead of 
the interface hierarchy so that covariance will work. That is, if the slice 
of an AbstractList is an AbstractList then the slice of a LinkedList can be 
a LinkedList.

/**  Interface Hierarchy
 *
 *   Enumeration(Value)
 *     IndexedEnumeration(Index,Value)
 *
 *   Container(Value) : Enumeration(Value)
 *     AssocContainer(Key,Value) : IndexedEnumeration(Key,Value)
 *     List(Value) : IndexedEnumeration(size_t,Value)
 *     Set(Value)
 *     MultiSet(Value)
 *     Stack(Value)
 *     Queue(Value)
 */

/**  Class Hierarchy
 *
 *  AbstractContainer(Value) : Container!(Value)
 *    AbstractAA(Key,Value) : AssocContainer(Key,Value)
 *      ConcurrentAA
 *      HashTable
 *      SortedAA
 *      LinkedAA
 *    AbstractList(Value) : List(Value)
 *      LinkedList
 *      ArrayList
 *      Deque
 *      CircularList
 *      SList
 *      CircularSList
 *    AbstractSet(Value) : Set(Value)
 *      HashSet
 *      SortedSet
 *      LinkedSet
 *    AbstractMultiSet(Value) : MultiSet(Value)
 *      HashMultiSet
 *      SortedMultiSet
 *      LinkedMultiSet
 *    AbstractStack(Value) : Stack(Value)
 *      ArrayStack
 *      DequeStack
 *      LinkedStack
 *    AbstractQueue(Value) : Queue(Value)
 *      ArrayQueue
 *      DequeQueue
 *      LinkedQueue
 *      PriorityQueue
 */

Aug 24 2005