FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Mango Containers
Goto page Previous  1, 2, 3, 4, 5, 6  Next
 
Post new topic   Reply to topic     Forum Index -> Mango
View previous topic :: View next topic  
Author Message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Thu Jul 21, 2005 9:48 pm    Post subject: Reply with quote

teqdruid wrote:
I see you're back, Kris. How was the vacation?

I haven't had much time to devote to Mango- I've been crazy busy lately. I've got more stuff that I haven't committed yet, but please let me know if you like the direction the Containers stuff is headed in.

Will definately take a gander, and get back to you. Probably over the weekend.

Had a nice break, thank you. I've always fancied driving across the country, and 4300 miles (total) went by more quickly than expected. Some of the National Parks are awe-inspiring, as were some of the lightning storms encountered.

Took a diversion at one point and went mountain-climbing in the vehicle (a Land Rover). Was about half way up a steep boulder-strewn ledge, with no possible hope of turning around, when I remembered there was an entire collection of wedding gifts in the back ... umm, <whoops>. Had volunteered to transport 'em, avoiding possible breakage via UPS/Post. Everything survived unscathed Smile
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Jul 27, 2005 10:47 pm    Post subject: Reply with quote

teqdruid wrote:
I've got more stuff that I haven't committed yet, but please let me know if you like the direction the Containers stuff is headed in.

I just took gander over the design and it all looks cool to me. Only wart I noticed (if I might call it that) would be the concat() series in the Container base-class ~ MutableX is a subclass of that one, and implements the concat() methods by creating a copy of the contents before adding the new stuff ~ if the container is a Mutable type, why does concat() create a new instance?

I guess I'm suggesting the concat() series be considered purely a mutable group of methods, rather than being applicable to immutable classes also? If so, they would belong outside of the Container base-class? Immutable classes could always do a .dup().concat() instead?

Other than that, it looks great!

Anyone else have a perspective on this? Eric?
Back to top
View user's profile Send private message
teqdruid



Joined: 11 May 2004
Posts: 390
Location: UMD

PostPosted: Thu Jul 28, 2005 9:01 pm    Post subject: Reply with quote

kris wrote:
I just took gander over the design and it all looks cool to me. Only wart I noticed (if I might call it that) would be the concat() series in the Container base-class ~ MutableX is a subclass of that one, and implements the concat() methods by creating a copy of the contents before adding the new stuff ~ if the container is a Mutable type, why does concat() create a new instance?


Immutable containers need some way to combine, and create a third one. For instance, I might want to do:
Code:
ImmutableList a = ...;
ImmutableList b = ...;
ImmutableList c = a ~ b;


Or, more likely:
Code:
List a = someMethod();
List b = someOtherMethod();
List everything = a ~ b;


However, if you have a MutableX you can do:
Code:
List a = someMethod();
MutableList b = myMethod();
b.append(a);


Quote:
I guess I'm suggesting the concat() series be considered purely a mutable group of methods, rather than being applicable to immutable classes also? If so, they would belong outside of the Container base-class? Immutable classes could always do a .dup().concat() instead?

No. They can't. ImmutableX.dup returns ImmutableX, so it doesn't have a concat.

The idea here is the concat is an immutable method that returns a new container, just like intersection. Both of them also have mutable equivalents (append and insersect) if you have a MutableX and it's acceptable to change it.

The most confusing thing I see here is the naming. Is concat generally though to mutate a container? If so, what should I change the name to?
Back to top
View user's profile Send private message Send e-mail AIM Address
teqdruid



Joined: 11 May 2004
Posts: 390
Location: UMD

PostPosted: Thu Jul 28, 2005 9:07 pm    Post subject: Immutables Reply with quote

Oh yes... I forgot to ask: have you looked at my ImmutableList? In theory it was a topic of much confusion and debate, so I'm wondering what you think of my implementation, and if it clears up any of my ideas.
Back to top
View user's profile Send private message Send e-mail AIM Address
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Fri Jul 29, 2005 8:23 am    Post subject: Reply with quote

kris wrote:
Anyone else have a perspective on this? Eric?


I like the implementation so far, but I haven't had a chance to use it in a practical setting yet. Last I tried, the code was immature and wouldn't compile, so I left it at that. Smile

As far as maps and lists go, D gives us a lot with built in arrays and such. The only things I find that I need beyond that are:

- Linked-Lists for avoiding duplication via COW
- Self-sorting or Priority-based behaviors
- Stack, Queue or Circular List/Buffer behaviors
- Smart map 'getters' that return a default value if a key is absent
- Syncronization, usually of the "read/write lock with write priority" flavor

... which usually drive me toward a custom container or at least array pseudo-members (via that nice syntactic loophole in D).

I really think its edge-cases like this that are imporant when building a good generic container lib; providing immutable support is just one. So I'm glad to see that the current design doesn't exclude the possibilty of classes with these behaviors. But is there any chance that we may see some of these added at a later time? Smile

That having been said, there are some great things already going on in this code. I especially like the Container.opApply() implementation, that uses a call to Iterator() internally. Also, the class tree looks pretty well normalized, although you may want to break some of those classes out into multiple files.
_________________
-- !Eric.t.Anderton at gmail
Back to top
View user's profile Send private message Yahoo Messenger
teqdruid



Joined: 11 May 2004
Posts: 390
Location: UMD

PostPosted: Sat Jul 30, 2005 2:05 pm    Post subject: Reply with quote

Quote:
I really think its edge-cases like this that are imporant when building a good generic container lib; providing immutable support is just one. So I'm glad to see that the current design doesn't exclude the possibilty of classes with these behaviors. But is there any chance that we may see some of these added at a later time?

I did my best to not just not exclude the possibility of these cases, but encourage them. I tried to make it as easy as possible to create a new implementation for each of the container types. As to whether or not I'll be implementing any of these cases, let me say "maybe". I've already implemented a doubly-linked list (although it doesn't implement COW) , and I've been planning on writing thread-safe wrapper classes for each type. When I'll get to the threading stuff, if ever, is the question. (The other question is whether or not I have the expertise to do it correctly Smile )

Quote:
although you may want to break some of those classes out into multiple files.

I've seperated stuff into files that people are most likely to use together. I didn't want to create List.d, AbstractList.d, MutableList.d, AbstractMutableList.d, ListIterator.d, and MutableListIterator.d all just for Lists, since a lot the them are real short, don't terribly pollute the namespace, and frequently people using one of them will want to use the others. That being said, I'm not terribly adverse to breaking them out if there's a good reason. Which classes were you referring to, specifically?

Quote:
... which usually drive me toward a custom container or at least array pseudo-members (via that nice syntactic loophole in D).

Like I eluded to earlier, it's my hope that (once I realease this) when people feel the need for a custom container, they'll implemented one of Mango's container types, so that their container will inter-operate with other code. Plus, since the AbstractX classes implement some methods, it should make the custom containers easier to write, and more fully-functional. What syntactic loophole are you referring to? The void myMethod(array[] a, params here); a.myMethod(params)?
Back to top
View user's profile Send private message Send e-mail AIM Address
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Sun Jul 31, 2005 8:37 pm    Post subject: Reply with quote

I'll paraphrase in the interest of making a shorter post. Please correct me if I miss the point. Smile

Quote:
I've been planning on writing thread-safe wrapper classes for each type. When I'll get to the threading stuff, if ever, is the question. (The other question is whether or not I have the expertise to do it correctly Smile )


And it should probably wait for a bit anyway since D is lacking a quality syncronization mechanism; the "synchronized" construct doesn't always cut it. I also find Ben's port of Doug Lea's model to be a little too obtuse for my blood, so maybe waiting for something better is a wise thing to do.

Quote:

I've seperated stuff into files that people are most likely to use together. That being said, I'm not terribly adverse to breaking them out if there's a good reason. Which classes were you referring to, specifically?


None in particular. I was actually thinking more in terms of style than anything else, what with this being a "Mango-style" class tree. Grouping by utility also makes a good deal of sense; I just wasn't seeing that at first glance. Please ignore my original comment.

Quote:
What syntactic loophole are you referring to? The void myMethod(array[] a, params here); a.myMethod(params)?


The very same. I ran across this today on the DNG, and it illustrates just how flexible this approach can be:

http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/27194

Andrew did an amazing job twisting D's symbol matching around using templates and aliases to create nearly invisible extensions to standard arrays. It has its drawbacks, but I just can't escape just how clever it is.
_________________
-- !Eric.t.Anderton at gmail
Back to top
View user's profile Send private message Yahoo Messenger
Stefan



Joined: 15 May 2005
Posts: 8

PostPosted: Mon Aug 01, 2005 7:53 am    Post subject: synchronized doesn't cut it?? Reply with quote

pragma wrote:

And it should probably wait for a bit anyway since D is lacking a quality syncronization mechanism; the "synchronized" construct doesn't always cut it.


I'm new to D. Could you please expand a bit further?
What's wrong with synchronized?

Kind regards,
Stefan
Back to top
View user's profile Send private message
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Tue Aug 02, 2005 11:55 am    Post subject: Re: synchronized doesn't cut it?? Reply with quote

Stefan wrote:
pragma wrote:

And it should probably wait for a bit anyway since D is lacking a quality syncronization mechanism; the "synchronized" construct doesn't always cut it.


I'm new to D. Could you please expand a bit further?
What's wrong with synchronized?

Kind regards,
Stefan


Sure! Smile

While it provides a good deal of flexibilty syntactially, it assumes that all you want is a Mutual-Exclusion lock (mutex). If you want a read/write lock of any kind, you need to build it up from scratch by using 'synchronized' or some other mechanism (like Ares' Atomic type).

A good exmaple of this is the Dll cache that is in DSP. Right now, it uses synchronized which makes the threads read or write in single-file; not good for a webserver. What it really needs is a read/write lock that will let any number of threads read simultaneously and will also only let one thread write at any one time (a write-preference lock).
_________________
-- !Eric.t.Anderton at gmail
Back to top
View user's profile Send private message Yahoo Messenger
Stefan



Joined: 15 May 2005
Posts: 8

PostPosted: Tue Aug 02, 2005 12:37 pm    Post subject: Re: synchronized doesn't cut it?? Reply with quote

pragma wrote:

While it provides a good deal of flexibilty syntactially, it assumes that all you want is a Mutual-Exclusion lock (mutex).


Ah ok, I see what you mean now - that's the situation I'm familiar with from Java. I was under the impression that you implied that D's synchronized might be broken somehow. Good to hear that's not the case :)

BTW, what are your concerns with Ben Hinkle's port of Doug Lea's library?
I didn't have a look at the D port, but I know Lea's library (it's part of JDK 5 now : java.util.concurrent). I think it addresses some of your points quite well?

Thanks for the clarification!
Stefan
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Tue Aug 02, 2005 2:07 pm    Post subject: Re: synchronized doesn't cut it?? Reply with quote

Stefan wrote:
pragma wrote:

While it provides a good deal of flexibilty syntactially, it assumes that all you want is a Mutual-Exclusion lock (mutex).


Ah ok, I see what you mean now - that's the situation I'm familiar with from Java. I was under the impression that you implied that D's synchronized might be broken somehow. Good to hear that's not the case Smile

BTW, what are your concerns with Ben Hinkle's port of Doug Lea's library?
I didn't have a look at the D port, but I know Lea's library (it's part of JDK 5 now : java.util.concurrent). I think it addresses some of your points quite well?

Thanks for the clarification!
Stefan

Ben's port of java.util.concurrent, with some updates and fixes, also resides in the mango.locks package. What Sean is building offers some more fine-grained control, and is seemingly targeted at a somewhat lower level than Prof Lea's library. I think the two are complementary, and will probably ask Sean to help me modify mango.locks appropriately.
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Tue Aug 02, 2005 2:17 pm    Post subject: Re: synchronized doesn't cut it?? Reply with quote

pragma wrote:
Stefan wrote:
pragma wrote:

And it should probably wait for a bit anyway since D is lacking a quality syncronization mechanism; the "synchronized" construct doesn't always cut it.


I'm new to D. Could you please expand a bit further?
What's wrong with synchronized?

Kind regards,
Stefan


Sure! Smile

While it provides a good deal of flexibilty syntactially, it assumes that all you want is a Mutual-Exclusion lock (mutex). If you want a read/write lock of any kind, you need to build it up from scratch by using 'synchronized' or some other mechanism (like Ares' Atomic type).

A good exmaple of this is the Dll cache that is in DSP. Right now, it uses synchronized which makes the threads read or write in single-file; not good for a webserver. What it really needs is a read/write lock that will let any number of threads read simultaneously and will also only let one thread write at any one time (a write-preference lock).

Good point, Eric.

BTW: have you considered using Prof Lea's concurrent HashMap for this purpose? The code implements a segmented hashmap to reduce lock-clashes, and (I vaguely recall) embellishes with a pseudo read/write lock mechanism. Mango.cache has a ported version of it, if you want to take a look.
Back to top
View user's profile Send private message
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Tue Aug 02, 2005 7:07 pm    Post subject: Re: synchronized doesn't cut it?? Reply with quote

kris wrote:

BTW: have you considered using Prof Lea's concurrent HashMap for this purpose? The code implements a segmented hashmap to reduce lock-clashes, and (I vaguely recall) embellishes with a pseudo read/write lock mechanism. Mango.cache has a ported version of it, if you want to take a look.


I have and I did; Lea's code is phenomenal, if it is a bit hard to follow in places.

I wound up going with a custom implementation, due to some vague problem in the Mango version (is all this coding affecting our memories?); something about it was insufficent. I also implemented a prioritization scheme inspired by what you had in one of your cache classes as well... which has, as I later found out, effectively reduced the whole mess to being single threaded since each read access results in a write. Embarassed

(as it is, there are more pressing issues to that project at present, but that's for that other board)
_________________
-- !Eric.t.Anderton at gmail
Back to top
View user's profile Send private message Yahoo Messenger
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Aug 03, 2005 11:44 am    Post subject: Re: synchronized doesn't cut it?? Reply with quote

pragma wrote:
kris wrote:

BTW: have you considered using Prof Lea's concurrent HashMap for this purpose? The code implements a segmented hashmap to reduce lock-clashes, and (I vaguely recall) embellishes with a pseudo read/write lock mechanism. Mango.cache has a ported version of it, if you want to take a look.


I have and I did; Lea's code is phenomenal, if it is a bit hard to follow in places.

I wound up going with a custom implementation, due to some vague problem in the Mango version (is all this coding affecting our memories?); something about it was insufficent. I also implemented a prioritization scheme inspired by what you had in one of your cache classes as well... which has, as I later found out, effectively reduced the whole mess to being single threaded since each read access results in a write. Embarassed

(as it is, there are more pressing issues to that project at present, but that's for that other board)

You're right ... layering a prioritization queue atop of the HashMap does single-thread the whole thing, since the queue is minimally updated per access ...
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Fri Aug 05, 2005 7:03 pm    Post subject: Reply with quote

teqdruid wrote:
kris wrote:
I just took gander over the design and it all looks cool to me. Only wart I noticed (if I might call it that) would be the concat() series in the Container base-class ~ MutableX is a subclass of that one, and implements the concat() methods by creating a copy of the contents before adding the new stuff ~ if the container is a Mutable type, why does concat() create a new instance?


Immutable containers need some way to combine, and create a third one. For instance, I might want to do:
Code:
ImmutableList a = ...;
ImmutableList b = ...;
ImmutableList c = a ~ b;


Or, more likely:
Code:
List a = someMethod();
List b = someOtherMethod();
List everything = a ~ b;


However, if you have a MutableX you can do:
Code:
List a = someMethod();
MutableList b = myMethod();
b.append(a);


Quote:
I guess I'm suggesting the concat() series be considered purely a mutable group of methods, rather than being applicable to immutable classes also? If so, they would belong outside of the Container base-class? Immutable classes could always do a .dup().concat() instead?

No. They can't. ImmutableX.dup returns ImmutableX, so it doesn't have a concat.

The idea here is the concat is an immutable method that returns a new container, just like intersection. Both of them also have mutable equivalents (append and insersect) if you have a MutableX and it's acceptable to change it.

The most confusing thing I see here is the naming. Is concat generally though to mutate a container? If so, what should I change the name to?

I think you nailed that one ~ it is just a naming thing, though I'm stumped to think of a more appropriate term right now ... uhhh ... 'combine' perhaps?
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Mango All times are GMT - 6 Hours
Goto page Previous  1, 2, 3, 4, 5, 6  Next
Page 4 of 6

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group