220 40668 article Path: news.gmane.org!.POSTED!not-for-mail From: holmes.odin@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Clusters instead of std::list and std::map! Date: Sat, 20 Oct 2018 16:59:10 -0700 (PDT) Lines: 216 Approved: news@gmane.org Message-ID: References: <3c8fb242-bdde-1ee8-878f-94bfb3ae084c@eld.physics.LeidenUniv.nl> <5888e4a7-3ed3-4759-969e-30211027e7b0@isocpp.org> <8cd19c2f-3a6d-4943-b18e-625b6cc6ee95@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_4054_1644204136.1540079950381" X-Trace: blaine.gmane.org 1540079827 14996 195.159.176.226 (20 Oct 2018 23:57:07 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 20 Oct 2018 23:57:07 +0000 (UTC) Cc: holmes@auto-intern.de To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBD6JXPHLXAKRBT4CV7PAKGQEL5JBYEY@isocpp.org Sun Oct 21 01:57:03 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yb1-f200.google.com ([209.85.219.200]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gE178-0003nj-Cf for gclcip-std-proposals@m.gmane.org; Sun, 21 Oct 2018 01:57:02 +0200 Original-Received: by mail-yb1-f200.google.com with SMTP id f8-v6sf21971665ybn.22 for ; Sat, 20 Oct 2018 16:59:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=wI95WxiyqMqxgp7ZzRYHFLkvHgfrbjOU76ZVlBF0+3A=; b=biVmL58epIu2zOHDio5TD4EucqshnLGFpZY/PkWIJefDq5HWiCBFf3cur8EnuPZSFq OVC1zmfqOyv6NknmrFnHRsdDqmNw9KkBKWmmg0lcbh9Y6DI21QPwimU/HgRvQYek8GXB UxcpCQdpn9SxuqMLkQ57HJ9wA+IxTtKYF3LFTx409r5U3xbLvF3SpFCur/6gUoOvT3VV lg//kOmM2NLi/9yeSyFvyFIGtCxC//JETPtxQf++R+CiTuaCpEsRcyec5xwjLyTWaURf m2eSqeYqMtaZ7MTyu+RyS8BL03vOiKHGNrNR9/u5Z8bWUMqY9d5f94CLhQhj904+DCvS U2lQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=wI95WxiyqMqxgp7ZzRYHFLkvHgfrbjOU76ZVlBF0+3A=; b=qMGP7YK+Tc1hJRQYhp1wJPTpRHzOct3SvDcg9w557pc6Zj9FgTpbrrcXDe2G7YgG6/ BkVgxyphdPa3zpwDyHVM/LPSiq1snkekzR55tb9tcOmomkuNmoZcYCe/hrEul/lDJrrN 2eY4gBLUrUKoDc4uRkpFfzwveejIbPRZJOyXDowuSIXZzpGeRQ1PM/dQVlGp+fbYugbi 7zv5hz5DcIVlzNverCMi1DfLtgVQkppFhQ437xDsoilOKHjJwWg60sZogHUIk4RgefO3 G7u+Qx5C/lCAB5dKJq6KmhalK/PEBnsTdsCp3Oo4Ua+awLMMFK8WJH9LJ8frfxwYke1E xipw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:x-original-sender:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=wI95WxiyqMqxgp7ZzRYHFLkvHgfrbjOU76ZVlBF0+3A=; b=MpSwhA6AAKpNviJumpl6UIBE7Zxc8pFs2hqBHhJqMDs9d0FJ2EWhU3LVmvs16WNc6Z 2G+S9ZXW7quyoL4YY/chxdLJZDD8suSXZd1DmdEFpdoXIY7HGTjdn94GOdXWdHVgJMKb JIryACkCl3GTruTSQtsimoHDxr93tJ1xhTi9smvOuCJzsP0E78hlWRtOmLrO/JyA8xkj 3zeH4qnYcrTuqvSQbraBQWkCli6dCY6nT2Q2egnaolhj1X0MGWqSmt+RW4hmpljpMGMF 8lAsEDg9pg2rKPk/u4v7i5FblCcE8S5g3SB7RNLinjiCPytlTuEpmIk4Oh0B9M3ObLIA OAlw== X-Gm-Message-State: ABuFfohV3VVTVUV2LLGyfQGHE1DFC4xecFA7glksNqD5Qr0qUHeG2KeD zF9NVMxqdiArzfmppseRuwpw+g== X-Google-Smtp-Source: ACcGV63dS4hKu8tWzleaDPX1WLl80Z8IzAHlQW30JLwvc9uhbGcYmTmVCQ7mHHV/A0Hgp2Vxb/EDsg== X-Received: by 2002:a25:b18d:: with SMTP id h13-v6mr23318159ybj.28.1540079952711; Sat, 20 Oct 2018 16:59:12 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:3984:: with SMTP id g126-v6ls14712091ywa.4.gmail; Sat, 20 Oct 2018 16:59:11 -0700 (PDT) X-Received: by 2002:a81:1a07:: with SMTP id a7-v6mr447985ywa.1.1540079951191; Sat, 20 Oct 2018 16:59:11 -0700 (PDT) In-Reply-To: X-Original-Sender: holmes.odin@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:40668 Archived-At: ------=_Part_4054_1644204136.1540079950381 Content-Type: multipart/alternative; boundary="----=_Part_4055_1149968836.1540079950381" ------=_Part_4055_1149968836.1540079950381 Content-Type: text/plain; charset="UTF-8" Hello Sven, I had a look at your code and I think I understand how it works inside. It looks like an implementation of a b-tree with the 'order' template-able and defaulted to 100. There are a few things which I noticed about the implementation but that's not important here (I'll post issues on your GitHub repo). What's interesting from a standardization standpoint is the public interface as well as the guarantees/requirements http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf see section 26 and think about how your container fits in (which guarantees it fulfills and which it can't). Having a working implementation is a plus but the real work will be coming up with a proposal/wording etc. This might be interesting for SG14 (we have looked at enough other proposals, this would play nice with pool allocators, caching etc.) but you should read the standard and try to come up with wording in a similar form. Feel free to contact me in German if that's easier for you. Best, Odin Am Sonntag, 21. Oktober 2018 01:09:06 UTC+2 schrieb Bryce Adelstein Lelbach: > > Adding Odin. > > On Sat, Oct 20, 2018, 3:12 PM > wrote: > >> I've written a standard-implementation and moved it to >> http://github.com/svenbieg/clusters. >> I think this is also the right place for the specification. >> >> In a cluster, iterator-stability doesn't seem to be so important, because >> iterators can be set to any position. >> The absolute position can be saved, the cluster can be changed, and the >> iterator can be reset to the previous item. >> In a multi-threaded environment the operations can be synchronized, like >> i've done in Clusters-Runtime. >> Mr. Gustafsson mentioned, if groups would have parent-pointers, the >> iterators would not have to allocate. >> This is right, but they still would not be stable. I think it's better to >> keep the clusters as small as possible. >> >> A custom allocator would have to be faster than the default. I'm thinking >> of a memory-manager using clusters, >> making custom allocators unnecessary. >> >> A very interesting feature is the sublist-splicing, wich You suggested. >> I'm going to implement this, but i didn't make it by now. >> I thought of insert- and remove-many, having large text-files doing >> replacements. >> Splicing out a sub-list is possible in constant-low time in a cluster. >> >> Combination of data-structures is another interesting feature You >> mentioned. >> Some functions are still missing, like insert-many and remove-many, >> splice-out, Thank You, and maybe some boolean functions for indices. >> This can be done with high-performance, but i didn't make, too. >> >> I think i misunderstood You with lower- and upper-bound. >> You can use an absolute position and a counter in clusters. >> >> The user can pass invalid arguments now, i've added some exceptions. >> I've also added the noexcept-keyword to read-only functions, >> it is necessary for std::move_if_no_except, wich is also still missing. >> >> Maybe some one on this list can have a look at the code? >> Some pieces might be very un-professional. >> Today i've read of std::move_if_no_except for the first time. >> >> I'm going to write a specification, i got some ideas already. >> Pictures say more than words, i think. >> >> Sven >> >> -- >> 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/8cd19c2f-3a6d-4943-b18e-625b6cc6ee95%40isocpp.org >> >> . >> > -- 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-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/f251c914-4200-48dc-a6b5-360319391bf5%40isocpp.org. ------=_Part_4055_1149968836.1540079950381 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hello Sven,

I had a look at your code a= nd I think I understand how it works inside. It=C2=A0looks like an implemen= tation of a b-tree with the 'order' template-able and defaulted to = 100. There are a few things which I noticed about the implementation but th= at's not important here (I'll post issues on your GitHub repo). Wha= t's interesting from a standardization standpoint is the public interfa= ce as well as the guarantees/requirements=C2=A0http://www.open-std.org/jtc1= /sc22/wg21/docs/papers/2017/n4659.pdf see section 26 and think about how yo= ur container fits in (which guarantees it fulfills and which it can't).= Having a working implementation is a plus but the real work will be coming= up with a proposal/wording etc. This might be interesting for SG14 (we hav= e looked at enough other proposals, this would play nice with pool allocato= rs, caching etc.) but you should read the standard and try to come up with = wording in a similar form. Feel free to contact me in German=C2=A0if that&#= 39;s easier for you.

Best,
Odin

A= m Sonntag, 21. Oktober 2018 01:09:06 UTC+2 schrieb Bryce Adelstein Lelbach:=
Adding Odin.=

On Sat, Oct 20, 2018,= 3:12 PM <sven...@web.de> wrote:
I've written a standard-implementation and mo= ved it to http://github.com/svenbieg/clusters.
I think this is also the right place for the specification.

In a cluster, iterator-stability doesn't seem t= o be so important, because iterators can be set to any position.
= The absolute position can be saved, the cluster can be changed, and the ite= rator can be reset to the previous item.
In a multi-threaded envi= ronment the operations can be synchronized, like i've done in Clusters-= Runtime.
Mr. Gustafsson mentioned, if groups would have parent-po= inters, the iterators would not have to allocate.
This is right, = but they still would not be stable. I think it's better to keep the clu= sters as small as possible.

A custom allocator wou= ld have to be faster than the default. I'm thinking of a memory-manager= using clusters,
making custom allocators unnecessary.
=
A very interesting feature is the sublist-splicing, wich You= suggested.
I'm going to implement this, but i didn't mak= e it by now.
I thought of insert- and remove-many, having large t= ext-files doing replacements.
Splicing out a sub-list is possible= in constant-low time in a cluster.

Combination of= data-structures is another interesting feature You mentioned.
So= me functions are still missing, like insert-many and remove-many,
splice-out, Thank You, and maybe some boolean functions for indices.
=
This can be done with high-performance, but i didn't make, too.

I think i misunderstood You with lower- and upper-bo= und.
You can use an absolute position and a counter in clusters.<= /div>

The user can pass invalid arguments now, i've = added some exceptions.
I've also added the noexcept-keyword t= o read-only functions,
it is necessary for std::move_if_no_except= , wich is also still missing.

Maybe some one on th= is list can have a look at the code?
Some pieces might be very un= -professional.
Today i've read of std::move_if_no_except for = the first time.

I'm going to write a specifica= tion, i got some ideas already.
Pictures say more than words, i t= hink.

Sven

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail 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/8cd19c2f-3a6d-4943-b18e-= 625b6cc6ee95%40isocpp.org.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/f251c914-4200-48dc-a6b5-360319391bf5= %40isocpp.org.
------=_Part_4055_1149968836.1540079950381-- ------=_Part_4054_1644204136.1540079950381-- .