Deterministic C++ memory manager

[Phil Bouchard]

Hi ISO C++,

I have developed a deterministic memory manager in C++ and I was wondering if ISO C++ would be interested to hear more about it.

For the moment I have included my solution in a brand new language I call "BB++" because I need to add functionality that C++ doesn't yet have such as:
- to add instances of an object implicitly as each scope;
- to add implicit references to these objects in top-level classes
- to overload 'operator .'
- to use 'auto' for member variables instead of 'decltype'
- to add metadata of the classes in order to propagate the proxy associated to the pointers within those classes

The homepage of my project is:
https://github.com/philippeb8/root_ptr/tree/bb++/bbpp2cpp

And I have a 17 minutes presentation available here:
https://youtu.be/GrNDYWyasxg

Please let me know if this is the type of research you are interested in. The work is a step away from being production ready. It has to be noted that Root.Ptr is already faster than Shared.Ptr in multithreaded mode.

Sincerely,
-Phil
https://github.com/philippeb8/root_ptr/tree/bb++/bbpp2cpp 

[Thiago Macieira]

On Friday, 4 August 2017 13:07:31 PDT Phil Bouchard wrote:
> I have developed a deterministic memory manager in C++ and I was wondering
> if ISO C++ would be interested to hear more about it.

To be clear to the rest of the mailing list: the allocator is not
deterministic. Only deallocation is deterministic -- as in, it's not a garbage
collection.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Arthur O'Dwyer]

It would help if you could edit down that YouTube video to cut all the dead air; it's 17 minutes of which the relevant 5 minutes is scattered around separated by painful silent sections. Even at 200% playback speed, it's a slog.

Certainly for your present purposes, nothing prior to 6m22s is relevant. (Anyone who cares already knows how mark-and-sweep and refcounting work, and doesn't need a tutorial on the subject.)

You never show code or diagrams for root_ptr in the video, but from the usage example and caveats, I infer that it is (almost?) exactly what Herb Sutter called a "deferred_heap" at CppCon 2016.

https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183

Of course everyone has their own implementation of this idea; and there are plenty of hybrids, such as "local arena allocators", or mixing in a bit of refcounting to get Objective-C's "autorelease pools", or mixing in a bit of RCU to get "RCU domains", or whatever.

Starting around 12m45s, the examples seem to be concerned entirely with showing examples of successful escape analysis — that is, you create a "node_proxy" (a.k.a. deferred_heap) and allocate some objects in that heap, and then you return a pointer to one of those objects from the current function. Normally this would cause dangling-pointer/use-after-free errors, but in this case your BB++ language is doing some sort of "escape analysis" to promote the returned object into the surrounding scope. Some explanation of this promotion mechanism would be useful, since it's the one thing that's not obvious how to do in today's C++.

my $.02,

–Arthur

[Phil Bouchard]

On Friday, August 4, 2017 at 6:40:45 PM UTC-4, Arthur O'Dwyer wrote:

On Friday, August 4, 2017 at 1:07:31 PM UTC-7, Phil Bouchard wrote:

Hi ISO C++,

I have developed a deterministic memory manager in C++ and I was wondering if ISO C++ would be interested to hear more about it.

For the moment I have included my solution in a brand new language I call "BB++" because I need to add functionality that C++ doesn't yet have such as:
- to add instances of an object implicitly as each scope;
- to add implicit references to these objects in top-level classes
- to overload 'operator .'
- to use 'auto' for member variables instead of 'decltype'
- to add metadata of the classes in order to propagate the proxy associated to the pointers within those classes

The homepage of my project is:
https://github.com/philippeb8/root_ptr/tree/bb++/bbpp2cpp

And I have a 17 minutes presentation available here:
https://youtu.be/GrNDYWyasxg

Please let me know if this is the type of research you are interested in. The work is a step away from being production ready. It has to be noted that Root.Ptr is already faster than Shared.Ptr in multithreaded mode.

It would help if you could edit down that YouTube video to cut all the dead air; it's 17 minutes of which the relevant 5 minutes is scattered around separated by painful silent sections. Even at 200% playback speed, it's a slog.

Certainly for your present purposes, nothing prior to 6m22s is relevant. (Anyone who cares already knows how mark-and-sweep and refcounting work, and doesn't need a tutorial on the subject.)

Thanks I'll make the corrections this weekend. 

 

You never show code or diagrams for root_ptr in the video, but from the usage example and caveats, I infer that it is (almost?) exactly what Herb Sutter called a "deferred_heap" at CppCon 2016.

https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183

Of course everyone has their own implementation of this idea; and there are plenty of hybrids, such as "local arena allocators", or mixing in a bit of refcounting to get Objective-C's "autorelease pools", or mixing in a bit of RCU to get "RCU domains", or whatever.

Firstly I would like to point out that I came up with the idea long before Microsoft did (2011 actually). You can easily find references to my previous attempts in the development Boost mailing list. Back in the days my library was called: "block_ptr" and "shifted_ptr".

Secondly deferred_ptr is not production ready and doesn't support multithreading mode whereas root_ptr was correctly unit tested and it does support multithreading mode but I just need to optimize one mutex (that is currently a static member) to make it even faster. 

 

Starting around 12m45s, the examples seem to be concerned entirely with showing examples of successful escape analysis — that is, you create a "node_proxy" (a.k.a. deferred_heap) and allocate some objects in that heap, and then you return a pointer to one of those objects from the current function. Normally this would cause dangling-pointer/use-after-free errors, but in this case your BB++ language is doing some sort of "escape analysis" to promote the returned object into the surrounding scope. Some explanation of this promotion mechanism would be useful, since it's the one thing that's not obvious how to do in today's C++.

I will clarify what is currently happening at that moment in my next video. Thanks for your patience.

Regards,

-Phil 

[Phil Bouchard]

> Certainly for your present purposes, /nothing/ prior to 6m22s is

> relevant. (Anyone who cares already knows how mark-and-sweep and
> refcounting work, and doesn't need a tutorial on the subject.)

Thanks I'll make the corrections this weekend.

> You never show code or diagrams for root_ptr in the video, but from the
> usage example and caveats, I infer that it is (almost?) exactly what
> Herb Sutter called a "deferred_heap" at CppCon 2016.
> https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183
> Of course everyone has their own implementation of this idea; and there
> are plenty of hybrids, such as "local arena allocators", or mixing in a
> bit of refcounting to get Objective-C's "autorelease pools", or mixing
> in a bit of RCU to get "RCU domains", or whatever.

Firstly I would like to point out that I came up with the idea long
before Microsoft did (2011 actually). You can easily find references to
my previous attempts in the development Boost mailing list. Back in the
days my library was called: "block_ptr" and "shifted_ptr".

Secondly deferred_ptr is not production ready and doesn't support
multithreading mode whereas root_ptr was correctly unit tested and it
does support multithreading mode but I just need to optimize one mutex
(that is currently a static member) to make it even faster.

> Starting around 12m45s, the examples seem to be concerned entirely with
> showing examples of successful escape analysis — that is, you create a
> "node_proxy" (a.k.a. deferred_heap) and allocate some objects in that
> heap, and then you return a pointer to one of those objects from the
> current function. Normally this would cause
> dangling-pointer/use-after-free errors, but in this case your BB++
> language is doing some sort of "escape analysis" to promote the returned
> object into the surrounding scope. Some explanation of this promotion
> mechanism would be useful, since it's the one thing that's not obvious
> how to do in today's C++.

[Phil Bouchard]

On Friday, August 4, 2017 at 6:40:45 PM UTC-4, Arthur O'Dwyer wrote:

In the following video, I am explaining how objects of a lower scope are being promoted to a higher scope (please fast forward to 10:15):
https://youtu.be/OBnpFUVEVe4

I added 5 slides explaining how objects are being promoted and I've renarrated everything after 6:21. I'm keeping the beginning because I am targeting newbies on the subject as well.

I hope that's a good explanation because sharing this information publicly is a point of no return for me.

Sincerely,

-Phil

[Thiago Macieira]

On Saturday, 5 August 2017 18:32:27 PDT Phil Bouchard wrote:
> I hope that's a good explanation because sharing this information publicly
> is a point of no return for me.

What do you mean by this?

[Phil Bouchard]

Well I don't have the protection of a software patent and if my library gets rejected by ISO then it'll surely be plagiarized by corporations.

[Thiago Macieira]

On Sunday, 6 August 2017 06:52:41 PDT Phil Bouchard wrote:
> Well I don't have the protection of a software patent and if my library
> gets rejected by ISO then it'll surely be plagiarized by corporations.

That's what copyright is for.

By the way, ISO is not interested in importing a library as-is. You need to
write a paper that describes what the implementation needs to do.

[Michał Dominiak]

This is actually not what copyright is for, though, which is apparent from a certain boost thread of the original poster. What he wants is a petent protection, but I don't believe this idea is anywhere near being as new as he thinks (and as would be in any sensible patent system to actually get a patent for it).

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/1702971.pEYQYCCQ6l%40tjmaciei-mobl1.

[Michał Dominiak]

Patent, not petent protection. Sorry, didn't catch that silly phone typo until I've already hit send.

[Phil Bouchard]

And a patent, I think, takes years to get which is a little bit counterproductive in the software industry.

[Phil Bouchard]

On Sunday, August 6, 2017 at 12:37:59 PM UTC-4, Thiago Macieira wrote:

On Sunday, 6 August 2017 06:52:41 PDT Phil Bouchard wrote:
> Well I don't have the protection of a software patent and if my library
> gets rejected by ISO then it'll surely be plagiarized by corporations.

That's what copyright is for.

By the way, ISO is not interested in importing a library as-is. You need to
write a paper that describes what the implementation needs to do.

Before I do write a paper, I was wondering if my presentation better described the solution I am putting forward.

[dgutson .]

Use a good free software license and if your library os good enough, people may pay you for support. 

To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f090ce52-3b6d-438b-ae87-01562a8ab6ef%40isocpp.org.

[Phil Bouchard]

Thanks for your advice but my goal is to create a library that doesn't need support ;)

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f090ce52-3b6d-438b-ae87-01562a8ab6ef%40isocpp.org.

[Nicol Bolas]

On Sunday, August 6, 2017 at 1:30:04 PM UTC-4, Phil Bouchard wrote:

And a patent, I think, takes years to get which is a little bit counterproductive in the software industry.

Some might argue that patents themselves are "counterproductive in the software industry", but that is neither here nor there. This discussion does raises an interesting question, however.

The C++ standard specifies behavior, not implementation. As such, what goes into the standard is not something that is patentable (I think?). However, implementation techniques could be patentable, and behavior is often informed by implementation techniques. As such, if the best (or only) technique for implementing a feature is encumbered by patents, and we know that even before standardizing it, is that something we want to standardize?

I certainly don't like the idea of C++ implementations being required to pay money or otherwise license something from a 3rd party just so that they can implement the standard with reasonable quality.

[Michał Dominiak]

I don't agree with the idea of patents for the software industry (and in a lesser extend, in other industries too) either, but regardless of that - OP seems to think that getting a thing into the standard will get him immortal fame, and getting others to implement a similar thing (which already happened, in multiple settings, from what I undestand) will be the worst thing ever.

Also, @Phil: in what way do you think a standard library component "doesn't need support"? if you think it doesn't you should talk to the implementers.

--

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/7adbfe8e-13f9-42d9-8916-e89456fc9d7f%40isocpp.org.

[Arthur O'Dwyer]

On Sun, Aug 6, 2017 at 12:17 PM, Michał Dominiak <gri...@griwes.info> wrote:
> I don't agree with the idea of patents for the software industry (and in a
> lesser extend, in other industries too) either, but regardless of that - OP
> seems to think that getting a thing into the standard will get him immortal
> fame, and getting others to implement a similar thing (which already
> happened, in multiple settings, from what I undestand) will be the worst
> thing ever.

Yeah; whereas in real life, generally you want several different implementations of an idea, and you want it to be used in production by a lot of people, before you feel safe calling it a "standard".

> Also, @Phil: in what way do you think a standard library component "doesn't
> need support"? if you think it doesn't you should talk to the implementers.

I believe that was just a humorous remark: he's saying his goal is to write bug-free, clear, documented, usable code, and then nobody will need to ask for support. That's my goal too. ;)  But your rebuttal is still accurate: in practice, every piece of code either dies without any support contracts, or lives long enough to see itself become the villain. :)

I think — I hope! — Phil wasn't suggesting that "if Boost adopts this library then I don't need to maintain it anymore." He was just saying (I hope) that "if I write really good code, then maintaining it will be easy."

(Note that I said "if Boost", not "if ISO", because "adopting libraries" is not really ISO WG21's business. ISO is in charge of specifications, not implementations. I think Phil has some misapprehension on that point also.)

–Arthur

[Tony V E]

ISO has rules about IP that cover this.

--

You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.

To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.

To post to this group, send email to std-pr...@isocpp.org.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/7adbfe8e-13f9-42d9-8916-e89456fc9d7f%40isocpp.org.

--

Be seeing you,

Tony

[Ville Voutilainen]

On 6 August 2017 at 22:10, Nicol Bolas <jmck...@gmail.com> wrote:
> I certainly don't like the idea of C++ implementations being required to pay
> money or otherwise license something from a 3rd party just so that they can
> implement the standard with reasonable quality.

To have something like that be standardized requires it to cure
cancer, and that might not
be sufficient. It would instantly turn off the ability of at least
one, if not multiple, implementation
vendors to ship an implementation, and would solicit fire and
brimstone of such proportions you've never
seen before in a C++ standardization context.

[Thiago Macieira]

On Sunday, 6 August 2017 10:30:04 PDT Phil Bouchard wrote:
> And a patent, I think, takes years to get which is a little bit
> counterproductive in the software industry.

If you want to file a patent on your root_ptr invention, it may already be too
late. You've been discussing its behaviour for the past several months in
multiple mailing lists. You should consult your patent attorney now and see if
you can still file a preliminary invention.

Of course, if you want this to become part of an ISO standard, you'll have to
allow anyone to use it royalty-free, forever.

[Phil Bouchard]

Let's put it in another way: I am obviously willing to support it but if I spend the next 10 years doing so then this means there is something wrong. If I just spend a year or two supporting it then this means my abstraction is solid.

[Phil Bouchard]

I understand ISO is a specification specialization and that's why I'm here. I would like to add the aforementioned features to the C++ language (implicit instantiations at each scope, metadata, etc.) so that I am able to make my implementation for Boost as clean as I present it with the BB++ language.

I also think these features could be applied to not only root_ptr's needs but will allow at lot a various useful derivatives. For example BB++ makes it very easy to apply a specialized template function to all member variables of a class using that metadata thing.

[Phil Bouchard]

I'll make the necessary efforts to make it part of ISO but I just want to be a 100% sure it doesn't end up plagiarized by some corporate business. I've seen all tactics after 17 years.

[Thiago Macieira]

On Sunday, 6 August 2017 19:41:43 PDT Phil Bouchard wrote:
> I understand ISO is a specification specialization and that's why I'm here.
> I would like to add the aforementioned features to the C++ language
> (implicit instantiations at each scope, metadata, etc.) so that I am able
> to make my implementation for Boost as clean as I present it with the BB++
> language.
>
> I also think these features could be applied to not only root_ptr's needs
> but will allow at lot a various useful derivatives. For example BB++ makes
> it very easy to apply a specialized template function to all member
> variables of a class using that metadata thing.

You'll need to explain what you need. This description above is not sufficient.

Please show what people do today, what the problem is with how they do it, and
how you'd like to change it (suggest a syntax, even if it won't work and we
need to change it).

[Thiago Macieira]

On Sunday, 6 August 2017 19:51:38 PDT Phil Bouchard wrote:
> I'll make the necessary efforts to make it part of ISO but I just want to
> be a 100% sure it doesn't end up plagiarized by some corporate business.
> I've seen all tactics after 17 years.

If it is part of ISO, then very many companies will implement it according to
your instructions. They do not have to give you credit.

You may provide a suitably-licensed implementation that encourages everyone to
adopt the code as-is, instead of rewriting from scratch. If you do that, then
your copyrights will remain in those implementations.

[Phil Bouchard]

Understood.

[Phil Bouchard]

Ok thank you very much. I'll use the following template:
http://open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3370.html

[Daniel Krügler]

2017-08-07 5:36 GMT+02:00 Phil Bouchard <phili...@gmail.com>:
> Ok thank you very much. I'll use the following template:
> http://open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3370.html

If you have any questions to the submission and allocation procedure,
please contact directly the lwgchair address (and use this address for
your document number allocation and proposal submission as well).
Unfortunately above paper is a bit outdated, but there does not exist
yet an update publicly available. The lwgchair address is available in
the ReplyTo field here:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html

Thanks,

- Daniel

[Phil Bouchard]

Perfect, thanks!

[Phil Bouchard]

Perfect, thanks!


-Phil

[Phil Bouchard]

On Saturday, August 5, 2017 at 12:22:48 PM UTC-4, Phil Bouchard wrote:

> You never show code or diagrams for root_ptr in the video, but from the
> usage example and caveats, I infer that it is (almost?) exactly what
> Herb Sutter called a "deferred_heap" at CppCon 2016.
> https://internals.rust-lang.org/t/herb-sutter-deferred-heaps-and-pointers/4183
> Of course everyone has their own implementation of this idea; and there
> are plenty of hybrids, such as "local arena allocators", or mixing in a
> bit of refcounting to get Objective-C's "autorelease pools", or mixing
> in a bit of RCU to get "RCU domains", or whatever.

Firstly I would like to point out that I came up with the idea long
before Microsoft did (2011 actually). You can easily find references to
my previous attempts in the development Boost mailing list. Back in the
days my library was called: "block_ptr" and "shifted_ptr".

To go back on this subject, root_ptr aka block_ptr aka shifted_ptr actually dates back from 2003!
http://boost.sourceforge.net/more/formal_review_schedule.html

 

Secondly deferred_ptr is not production ready and doesn't support
multithreading mode whereas root_ptr was correctly unit tested and it
does support multithreading mode but I just need to optimize one mutex
(that is currently a static member) to make it even faster.

Thirdly root_ptr injected via the powerful Clang-based Fornux C Leak Detector works well and has been tested with a modified version of libarchive:
https://github.com/philippeb8/libarchive/commit/5858b5c047301123ffdf05f247f7d191829d5a9b

The modifications involved are very simple but can be repetitive.

I think the next step is to standardize meta-data but not the way Mr. Sutter proposes it because like I was saying before, extra parameters will need to be passed to each function and extra member variables will need to be added to each top-level class and compilation unit. This meta-data can be used to get backtraces as well, like previously mentioned somewhere.

It is working well with the Fornux C Leak Detector and I will try to share a free version for Linux and Windows in the following months. Thanks for your patience... again.

Regards,

Phil Bouchard

www.fornux.com