On 4/4/2011 10:54 PM, Vicente BOTET wrote: [...]

...

I would like to request a review while I add the necessary documentation for a better support.

Hi Phil,

it is a shame that you have not had the time since 2 years to make the documentation. If you add Jamfiles and a complete tests sheet this will encourage others to look at you library.

It is clear that in the current state the library is not ready for review.

Thanks for the clarifications and sorry for not getting back into it faster than that but I've been working on a new theory (or law) in astrophysics called: Finite Relativism. For the interested, it covers Mercury's perihelion precession, the bending of light by gravity, the galaxy's rotational curve (yet unexplained by other theories), etc. I'll update the documentation and I'll come back when I'm done. Thanks, -Phil

On 4/5/2011 7:39 AM, Thomas Klimpel wrote:

Phil Bouchard wrote:

...

For those who are not aware in 2008 I wrote a memory manager running in real-time so that heap objects are being destructed instantly. A quick introduction can be found here: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/libs/smart_ptr/doc/ ShiftedPointer.ppt

How is this "memory manager" related to the "smart pointer" reviewed in 2003? <http://lists.boost.org/Archives/boost/2003/09/53333.php>

I reviewed the mentioned presentation, and I still don't get what "shifted_ptr" wants to be. The very first slide says "Shifted Pointer" ... "Deterministic Memory Manager of Constant Complexity". The next slide that even mentions "shifted_ptr" is slide 17: "Shifted Pointer - Advantages", and it just enumerates some "advantages", without first stating what "shifted_ptr" really is. Slide 18 and 19 show an example source code using "shifted_ptr" and its output, but still no explanation what "shifted_ptr" wants to be.

I think I'm able to guess what slides 20-27 try to illustrate, but even this wasn't immediately obvious. (You write in the presenters notes, that a red circle means that the objects get collected and destroyed. You could also add to example 2 and 4 notes that some unreferenced nodes didn't get collected immediately, probably for good reasons.) I also read through some of your comments from the review in 2003. I often couldn't understand what you said, and wondered whether it was because I was missing some context that "the participants" knew from prior discussions. At least today, nearly nobody will know the context anymore, so you definitively have to be much more concrete, and explain the context explicitly.

...

"shifted_ptr_test1" shows its versatility and simplicity while "t100_test1" shows a more complicated application on a neural network.

I would like to request a review while I add the necessary documentation for a better support.

It's great if you come up with good documentation.

But I would suggest a much easier step first. Your presentation already exists, and it has many nice pictures and illustrates many points. Yet I have the impression that it still fails to convey the information that also some of the reviewers missed in 2003. Why don't we try to "review" and improve this presentation first? To be honest, I would really like to know what "shifted_ptr" is (or wants to be). As there is already a 28 page presentation and many examples, this should hopefully be a goal that can be achieved.

I'll do the requested modifications...

To get started, let me ask some questions (based on the examples):

1) Is the class template "shifted_ptr" a shared pointer? Does it provide pointer semantics?

shifted_ptr<> derives from shifted_ptr_base<>, which is a shared pointer. shifted_ptr<> is therefore a shared pointer.

2) Is the class template "shifted_ptr" a proxy object? Does it provide object semantics?

shifted_ptr<> uses a proxy object called "set". A set is a group of pointers residing on the heap and pointing to each other (just like a STL container). A set will be merged with another one if one of its pointer refers to an object in the other set. A set is represented by a circle in the presentation.

3) Can the class template "shifted_ptr" act as smart array? Does it provide array semantics when instantiated with an array?

As we can see in shifted_ptr_test1.cpp when shifted_ptr<> is instanciated with an array, its parent shifted_ptr_base<> uses array semantics (replaces "operator *" by "operator []").

4) Is "shifted_ptr" intended to mean that it is pointer to "shifted"?

Yes.

5) Does "shifted" contain a refcount?

shifted<> derives from sp_counted_base, that defines the reference counter used by shared_ptr objects.

6) Does the class template "shifted_ptr" takes care of "shared ownership" (memory management)?

The ownership is indeed shared just like shared_ptr<> but shifted_ptr<> adds another layer of ownership shared with sets. shifted_ptr<> a therefore a complete memory manager because it prevents cyclic reference counting; if the last shifted_ptr<> pointing to a cyclic set is destroyed then the whole set is also destroyed.

As a hint, this is how the semantics of "shared_ptr" are sometimes described:

"The shared_ptr class template stores a pointer, usually obtained via new. shared_ptr implements semantics of shared ownership; the last remaining owner of the pointer is responsible for destroying the object, or otherwise releasing the resources associated with the stored pointer."

If you manage to come up with a similar description for "shifted_ptr", most of the above questions would probably be obsolete.

I finally have a question out of pure curiosity (leave it unanswered if you want): "Is the memory manager part of Shifted Ptr some form of reference counting (on a suitable scale), or is it more related to region based memory management, or is it original research completely unrelated to any known memory management strategies?"

No shifted_ptr<> uses its own memory management strategy on top of reference counting. Bests, -Phil

On 4/5/2011 1:50 PM, Dominique Devienne wrote:

On Tue, Apr 5, 2011 at 3:04 PM, Phil Bouchard<philippe@fornux.com> wrote:

...

No shifted_ptr<> uses its own memory management strategy on top of reference counting.

Phil, can you please explain the rational for the name shifted_ptr<>? Sounds more like a "managed" ptr to me, and don't see how that relates to "shifted".

In contrast with shared_ptr<> which has one pointer to the object and another one to the reference count, shifted_ptr<> only has one pointer to the object. The object is a member inside shifted<> and the reference count is accessed by shifting the pointer up to the reference count, a member preceding the object (defined in sp_counted_base). i.e.: class sp_counted_base // pointee header { int use_count_; int weak_count_; ... }; class owned_base : public sp_counted_base // pointee header { ... }; template <typename T> class shifted : public owned_base // pointee { T elem_; }; template <typename T> class shifted_ptr_common // pointer { T * po_; // directly points to a shifted<T>::elem_ ... owned_base * header() { // returns the counter by shifting "po_" up } };

Having done Java for a few years, I understand the GC concept you described in your previous post (wondering how you achieve O(1) ops and immediate destruction though :) ) and that you guarantee object one references won't be deleted, but the flip side is that unwanted references can prevent the whole ball-of-wax from ever being GC'd. There are several tools in Java to find those "reference" leaks, which is tricky in large applications, especially GUI ones. How does one tackle this issue with your _ptr<>?

A smart pointer object has the count of the number of pointers pointing to the object. shifted_ptr<> also has a set counter; a set counter has the count of the number of pointers from the stack referencing to the set. Thus when no pointers from the stack are referencing the set anymore then the set is being destroyed instantly.

Finally, when a "set" is GC'd, in which order are it's elements deleted? Of particular interest is the case with cycles of course. Is a "stale" _ptr<> (what it points to, in the same "set", was already deleted) in the soon-to-be deleted object reset to null implicitly kinda like weak_ptr<>?

The elements inside a set are being destroyed in the reverse order they were constructed. The destruction of a cyclic set is done by forcing all elements to be destroyed and disregards reference counts. Thanks, -Phil

On 4/5/2011 4:16 PM, Vicente BOTET wrote:

...

Message du 06/04/11 00:36 De : "Phil Bouchard"

...

A : boost@lists.boost.org Copie à : Objet : Re: [boost] [shifted_ptr] Review Request

A smart pointer object has the count of the number of pointers pointing to the object. shifted_ptr<> also has a set counter; a set counter has the count of the number of pointers from the stack referencing to the set. Thus when no pointers from the stack are referencing the set anymore then the set is being destroyed instantly.

Are shifted_ptrs thread safe?

The pools it uses are thread safe and so is the reference count but the manipulation of a set hasn't been tested yet in a multithreaded environment. Thanks, -Phil

On 4/5/2011 5:39 PM, Phil Bouchard wrote:

I just added descriptions on each page of the presentation explaining what is being demonstrated.

The following link isn't refreshed properly by Mozilla Firefox: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/libs/smart_ptr/doc/Shift... If I used Internet Explorer the latest PowerPoint presentation will be downloaded. -Phil

On 4/6/2011 11:23 AM, Thomas Klimpel wrote: [...]

...

Furthermore you'll also notice a problem with the Mark& Sweep algorithm on slides 7& 8, where a parent node still referencing a child node is being deleted. Slides 26& 27 shows how this is not a problem with shifted_ptr<>.

There is nothing wrong with deleting an unreferenced node that still references other nodes itself. Perhaps you fear that there might still be implicit references to the object, which are not tracked. So you probably have taken a "region based memory management" point of view here. (You "feel" that the region hasn't yet been left yet, because the child is still around, so you fear that deleting the parent might be a bad idea.) Still it isn't a problem in the context of Mark& Sweep.

Of course there is something wrong with this ;) Imagine the nodes in the presentation are widgets. If you have a parent window which has a child window or dialog window, but the parent window is unreferenced. The Mark & Sweep algorithm will simply wipe away the parent window and leave the child dialog box on its own. Bests, -Phil

On 4/6/2011 12:06 PM, Thomas Klimpel wrote:

Then the problem here is that the reference to the parent window went away. It's perfectly OK for the Mark& Sweep algorithm to wipe away unreferenced nodes.

If you have a modal dialog box, you don't want your main window to simply disappear just because there is no pointer pointing to it. -Phil

On 4/6/2011 12:43 PM, Thomas Klimpel wrote:

It's not just that there is no pointer pointing to the main window. At the moment were Mark& Sweep wipes the main window away, no references of any sort to the main window are left. So even if Mark& Sweep wouldn't wipe it away, it would be an unreachable object that couldn't be used anymore by the program (because the program has sort of forgotten the address of the object).

No reference to its data is left but the destruction of the window is premature. If the parent is incrementing a timer in the child widget, then the parent can't be destroyed before its child otherwise the timer will become inert. -Phil

On 4/6/2011 1:22 PM, Thomas Klimpel wrote:

If the parent is still able to do something (like incrementing a times in the child widget), then obviously references to the parent still exist. For Mark& Sweep, you are in a context where even every implicit reference is known to the garbage collector. It's clear that you can't strictly guarantee this for a C/C++ program. But in this case, the problem would be that an implicit reference went unnoticed by the Mark& Sweep garbage collector, not that it wiped an unreferenced node.

The timer was a bad example, forget about it. But in the case of the Mark & Sweep algorithm, a call to the parent window destructor will still be premature if the modal child dialog box still exists.

I have a bit the impression that you end up again talking more about another approach (Mark& Sweep in this case) than about the "Shifted Pointer" approach. That's OK for me, just don't blame me if you should find out later that this might have been a waste of time.

By comparing Shifted Pointer to other solutions then people might find it easier to understand because I'm talking their language. -Phil

On 4/6/2011 3:35 PM, Phil Bouchard wrote:

I think I made a mistake because Shifted Pointer will act like the Mark & Sweep and delete the unreferenced parent node. Sorry about the confusion, I'll make the modification to the presentation.

I just fixed the presentation. -Phil

On Wed, Apr 6, 2011 at 3:15 AM, Phil Bouchard <philippe@fornux.com> wrote:

- shared_ptr<> shouldn't be used for performance critical applications

Why not? -- Olaf

On Wed, Apr 6, 2011 at 10:51 AM, Phil Bouchard <philippe@fornux.com> wrote:

On 4/6/2011 1:08 AM, Olaf van der Spek wrote:

...

On Wed, Apr 6, 2011 at 3:15 AM, Phil Bouchard<philippe@fornux.com>  wrote:

...

- shared_ptr<>  shouldn't be used for performance critical applications

Why not?

You'll find a comparison in speed of all smart pointer types here and you will see "special" & "simple" counted being slower than intrusive_ptr: http://www.boost.org/doc/libs/1_46_1/libs/smart_ptr/smarttests.htm

All tests were run on a PII-200 running Windows NT version 4.0

IMO that means the results are meaningless. -- Olaf

On Wed, Apr 6, 2011 at 6:43 PM, Phil Bouchard <philippe@fornux.com> wrote:

On 4/6/2011 2:14 AM, Olaf van der Spek wrote:

...

...

You'll find a comparison in speed of all smart pointer types here and you will see "special"&  "simple" counted being slower than intrusive_ptr: http://www.boost.org/doc/libs/1_46_1/libs/smart_ptr/smarttests.htm

...

All tests were run on a PII-200 running Windows NT version 4.0

IMO that means the results are meaningless.

Here's another one here comparing shared_ptr<>, intrusive_ptr<> and garbage collected algorithms: http://hnxgc.harnixworld.com/benchmarks/GCBench/

What version of Boost was used? Does it use make_shared? Olaf

Actually, boost::make_shared involves one dynamic_cast operation (when getting deleter from shared_ptr object), that's why it doesn't perform faster at all 2011/4/6, Nevin Liber <nevin@eviloverlord.com>:

On 6 April 2011 11:43, Phil Bouchard <philippe@fornux.com> wrote:

...

http://www.boost.org/doc/libs/1_46_1/libs/smart_ptr/smarttests.htm

...

...

Here's another one here comparing shared_ptr<>, intrusive_ptr<> and garbage collected algorithms: http://hnxgc.harnixworld.com/benchmarks/GCBench/

Glancing at the code, I noticed that they aren't using make_shared or allocate_shared, which any real world high performance app would most likely be using just to cut the number of allocations in half. Not a great benchmark for this kind of thing... -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

AMDG On 04/06/2011 10:54 AM, Nevin Liber wrote:

2011/4/6 Юрій Зубрицький<mt.wizard@gmail.com>

...

Actually, boost::make_shared involves one dynamic_cast operation (when getting deleter from shared_ptr object), that's why it doesn't perform faster at all

Where exactly is that in the code? I don't see it in make_shared.hpp (1.46.1), and the uses inside shared_ptr.hpp look to be related to construction and dynamic_pointer_cast.

I assume that he's referring to the call to get_deleter. It doesn't actually do a dynamic_cast. It does a single type_info comparison.

I also surmise that dynamic_cast is still faster than heap allocation.

In Christ, Steven Watanabe