Interest in a flyweight library?
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns: http://tinyurl.com/l6lt4 The so-called Flyweight Design Pattern, upon which this is inspired, is much too OO for current C++ tastes IMHO, what I'm proposing takes a more generic stance. A minimal use example follows showing the syntax: #include "flyweight.hpp" #include <string> #include <iostream> int main() { using boost::flyweight::flyweight; flyweight<std::string> str("hello world"); std::cout<<str<<"\n"; } Briefly put, a flyweight<T> is an object that can be used as a const T (i.e. flyweight<T> provides an operator const T&) but whose size is that of a pointer. The trick is that identical flyweight<T> objects share their representation globally, which drastically reduces memory usage when there are much more objects than different values. Additionally, comparison of flyweight objects can be made faster than that of the underlying type T, since we it reduces to pointer comparison --contrast that with what takes to compare the underlinyg type T when T=std::string, for instance. So, is there interest in having such a lib in Boost? Please note that the provided implementation is still a primitive one, but OTOH it does have all the advertised functionality, so one can use it to test it locally and form an opinion about its suitability: if somebody, for instance, can plug it into some scenario with massive quantities of elements, I'd appreciate knowing about resulting memory and performance improvements. In case this raises interest, I can turn the thing into a more fleshed out proposal during the summer. Thank you for your attention, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
http://tinyurl.com/l6lt4 [snip]
So, is there interest in having such a lib in Boost?
Yes, I'm interested in it. Not sure if I can provide any feedback or usage experiences in a short time though. Best, Oleg Abrosimov.
On 6/28/06, Oleg Abrosimov <beholder@gorodok.net> wrote:
Joaquín Mª López Muñoz wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
http://tinyurl.com/l6lt4 [snip]
So, is there interest in having such a lib in Boost?
Me too... If it was included in Boost two years ago... It would have saved me a lot of time in one of my projects... :) Regards Matias
I hope i am not being too naive, but what differences are there between your proposal and shared_ptr ? I can definitely see the object vs pointer access difference ; are there others ? I am asking you this because, for the purpose you describe, i am currently using shared_ptr objects... Is it extremely wrong to do so ? Regards, Benoît
Hello Benoît, Benoit ha escrito:
I hope i am not being too naive, but what differences are there between your proposal and shared_ptr ? I can definitely see the object vs pointer access difference ; are there others ?
The main difference is that flyweight<T> enforces that *every* flyweight object with the same value will have a pointer to the same internal representation. shared_ptr does not provide any means to automatically get this behavior. For instance, you are free to do this: shared_ptr<string> p1(new string("hello")); shared_ptr<string> p2(p1); // p1 and p2 share rep shared_ptr<string> p3(new string("hello")); where p1 and p2 share their representation while p3 holds a string objects of its own. By contrast if you do: flyweight<string> f1("hello"); flyweight<string> f2(f1); flyweight<string> f3("hello"); the result is that f1,f2 and f3 internally point to the same "hello" string. This "coalescing" work is what flyweight gets you in comparison with shared_ptr. Of course, shared_ptr has a (wide) application domain of its own where such coallescing is neither needed nor acceptable. We are talking about different beasts.
I am asking you this because, for the purpose you describe, i am currently using shared_ptr objects... Is it extremely wrong to do so ?
It all depends on your particular usage scenario. If your app semantics guarantee that you cannot come up with a situation like the one described above, then flyweight buys you nothing with respect to shared_ptr. Otherwise, either you're having redundant copies around or else you have implemented a mechanism for duplicate checking --which is what flyweight internally does, of course. I hope I've made myself clear, please come back if I haven't.
Regards, Benoît
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz <joaquin@tid.es> writes:
The main difference is that flyweight<T> enforces that *every* flyweight object with the same value will have a pointer to the same internal representation.
Isn't this usually called "intern", at least when applied to strings?¹ I can see how "flyweight" captures the means of referring to the interned object, but the essential facility here is the interning, not the reference mechanism. Footnotes: ¹ http://www.lispworks.com/documentation/HyperSpec/Body/f_intern.htm http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html#intern() -- Steven E. Harris
"Steven E. Harris" ha escrito:
Joaquín Mª López Muñoz <joaquin@tid.es> writes:
The main difference is that flyweight<T> enforces that *every* flyweight object with the same value will have a pointer to the same internal representation.
Isn't this usually called "intern", at least when applied to strings?¹ I can see how "flyweight" captures the means of referring to the interned object, but the essential facility here is the interning, not the reference mechanism.
Well, at least in my experience I had never heard of that "intern" terminology. Reading the links you provide, seems to me like the term is used to refer to the factory part of the Flyweight Design Pattern, and the the pattern is somewhat broader than the intern thing only, as it accounts for other participating agents, see for instance. http://home.earthlink.net/~huston2/dp/flyweight.html If you want to see this way, the flyweight<...> class I'm proposing automates the Client part as described in the link above. Anyway, naming discussions aside, do you see value in such a thing being elaborated and eventually proposed to Boost?
Footnotes: ¹ http://www.lispworks.com/documentation/HyperSpec/Body/f_intern.htm http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html#intern()
-- Steven E. Harris
Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz <joaquin@tid.es> writes:
Anyway, naming discussions aside, do you see value in such a thing being elaborated and eventually proposed to Boost?
From my brief examination of the implementation and examples provided, yes, it looks useful. I have no qualms with the idea and I have full confidence you'll implement it well. However, I don't think you should cast the naming problem aside as immaterial.
The links I provided described the interning facility in two other languages. In discussing those other languages, we don't usually hear about strings or symbols being "flyweights". We do hear "symbols are interned" or "strings are interned". Expanding these statements could yield something more like, "Strings are flyweight references to a particular unique instance in a global pool." We're both arguing that there's prior art here to justify the name. Your implementation includes both a reference mechanism and a pooling mechanism. "Flyweight" describes the former, but the pattern, at least by my reading, doesn't speak to comparing candidate instances and ensuring that there are no duplicates in the pool. That duplicate-avoidance policy is specifically addressed by interning. My concern is that I might overlook this library because its name does not capture what I would value about it most. Clearly I have biases, having been exposed to the "intern" terminology for years, so perhaps we can hear from others as to whether the name is appropriate. -- Steven E. Harris
On 6/30/06, Steven E. Harris <seh@panix.com> wrote:
My concern is that I might overlook this library because its name does not capture what I would value about it most. Clearly I have biases, having been exposed to the "intern" terminology for years, so perhaps we can hear from others as to whether the name is appropriate.
I immediately thought of an "interned_string" class I had written when I read Joaquin's description. I have only really seen this technique called "interning" and (once) "coadunation" before. There is an implementation of something similar for strings only in the ASL called adobe::name_t: http://opensource.adobe.com/classadobe_1_1name__t.html I like this utility, but I agree it might be better named boost::interned<T>. -- Caleb Epstein
On 7/1/06, Caleb Epstein <caleb.epstein@gmail.com> wrote:
I like this utility, but I agree it might be better named boost::interned<T>.
I like the utlitity too, however I'm not really sure about "interned" -- having been exposed only to the GoF Flyweight pattern. Perhaps boost::interned<T> and boost::flyweight<T> can be made identical or behave the same? What I would be saying really is that boost::interned can apply the "value instance singularity" (invented phrase, something I try to describe how I understand what the library is doing) while boost::flyweight<T> be consistent with the GoF flyweight description? Would it be too much work to do this? -- Dean Michael C. Berris C/C++ Software Architect Orange and Bronze Software Labs http://3w-agility.blogspot.com/ http://cplusplus-soup.blogspot.com/ Mobile: +639287291459 Email: dean [at] orangeandbronze [dot] com
On 6/28/06, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
Wow, what an excellent little utility! I've written something similar in the past to do Java-style "string interning", but this is much more flexible and well written. Adding this to bag<tricks> now. -- Caleb Epstein
On 6/28/06, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
Additionally, comparison of flyweight objects can be made faster than that of the underlying type T, since we it reduces to pointer comparison
Very nice! A few comments: - What's y? void swap(flyweight& x) { std::swap(x.h,y.h); } - I'm not convinced operator< should be in terms of the pointer. x<y being different from (T&)x < (T&)y seems like an easy source of errors. ~ Scott McMurray <OT> Has anyone proposed a good way of doing wrapping for C++0x? That problem keeps coming up...
me22 ha escrito:
On 6/28/06, JoaquÃn Mª López Muñoz <joaquin@tid.es> wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
Additionally, comparison of flyweight objects can be made faster than that of the underlying type T, since we it reduces to pointer comparison
Very nice!
Thank you!
A few comments: - What's y? void swap(flyweight& x)
{
std::swap(x.h,y.h);
}
This is my error, please replace with std::swap(h,x.h); I've uploaded a corrected version of flyweight.hpp to the Vault.
- I'm not convinced operator< should be in terms of the pointer. x<y being different from (T&)x < (T&)y seems like an easy source of errors.
Yes, you've got a point here. My design ideas involve turning flyweight into a policy-controlled class so that the user can select this kind of things. I agree with you the default should be T-compatible operator< and only pointer-based when the user explicitly selects it.
~ Scott McMurray
<OT> Has anyone proposed a good way of doing wrapping for C++0x? That problem keeps coming up...
A poor man's approach to wrapping can be taken with Jonathan Turkanis' BIL library http://www.kangaroologic.com/interfaces/ which has also IMHO an immense potential for all kinds of applications. Unfortunately, seems like Jonathan is not actively pursuing promoting this into Boost :( Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On 6/28/06, Joaquín Mª López Muñoz <joaquin@tid.es> wrote:
During some conversations with a colleague I came up with a very sketchy realization of what could be converted, if there is interest, in a flyweight library. Please see flyweight.hpp at Vault/Patterns:
The so-called Flyweight Design Pattern, upon which this is inspired, is much too OO for current C++ tastes IMHO, what I'm proposing takes a more generic stance. A minimal use example follows showing the syntax:
#include "flyweight.hpp" #include <string> #include <iostream>
int main() { using boost::flyweight::flyweight;
flyweight<std::string> str("hello world"); std::cout<<str<<"\n"; }
Briefly put, a flyweight<T> is an object that can be used as a const T (i.e. flyweight<T> provides an operator const T&) but whose size is that of a pointer. The trick is that identical flyweight<T> objects share their representation globally, which drastically reduces memory usage when there are much more objects than different values. Additionally, comparison of flyweight objects can be made faster than that of the underlying type T, since we it reduces to pointer comparison
--contrast that with what takes to compare the underlinyg type T when T=std::string, for instance.
So, is there interest in having such a lib in Boost? Please note that the provided implementation is still a primitive one, but OTOH it does have all the advertised functionality, so one can use it to test it locally and form an opinion about its suitability: if somebody, for instance, can plug it into some scenario with massive quantities of elements, I'd appreciate knowing about resulting memory and performance improvements.
In case this raises interest, I can turn the thing into a more fleshed out proposal during the summer.
This library seems like it could be excellent, lets get a review going! As others have noted, of all the languages I have looked at, I've never heard the term "flyweight", only "interned". Where does "flyweight" come from? This library might get more recognition if it used the more common name.
Thank you for your attention,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Cory Nelson http://www.int64.org
On 7/1/06, Cory Nelson <phrosty@gmail.com> wrote:
As others have noted, of all the languages I have looked at, I've never heard the term "flyweight", only "interned". Where does "flyweight" come from?
Flyweight is a software design pattern as described by Gamma et al in _Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional Computing Series)_. Wikipedia also has a fine description: http://en.wikipedia.org/wiki/Flyweight_pattern Jon
participants (10)
-
Benoit -
Caleb Epstein -
Cory Nelson -
Dean Michael Berris -
Joaquín Mª López Muñoz -
Jonathan Franklin -
Matias Capeletto -
me22 -
Oleg Abrosimov -
Steven E. Harris