RFC: Deprecate libstdc++ Policy-Based Data Structures

RFC: Deprecate libstdc++ Policy-Based Data Structures

[Alexander Kulkov]

Hi there! I hope, this message will go to where it's expected to go, since
I'm not really familiar with e-mail threads.

I was the one who brought https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
issue about sub-optimal implementation of split function in pbds. The
reason why I did so is clearly described on this comment:
https://codeforces.com/blog/entry/10355?#comment-157883

So, a bit of story and context. Five years ago at codeforces.com
(competitive programming website) someone eventually pointed out that there
is order-statistics tree in SGI library. It turned out to be very useful in
competitions since it is quite common type of queries to count number of
elements less than k in set and unfortunately regular std::set doesn't
provide such possibility although it would be extremely useful in
competitions.

I made two posts about pbds on codeforces to introduce them to community:
https://codeforces.com/blog/entry/11080 and
https://codeforces.com/blog/entry/13279. First one introduces structures in
general and second one describes how to modify them so they support custom
queries. Second one was not quite as popular, perhaps because it's not much
easier to comprehend and remember concept than simply write something like
cartesian tree on live contest. But the first one is pretty much alive,
most recent comment was only 8 days ago.

There was also another post (https://codeforces.com/blog/entry/60737)
considering hash_map from pb_ds as a replacement for unordered_map since
hash_map clearly outperform unordered_map. This one is also quite popular
and well-known in competitive programming community.

So speaking about "Do you actually use these containers?" I would say that
I often use tree_order_statistics_node_update in competitions, and in
general specifically tree_order_statistics_node_update and hash_map are
pretty popular in competitive programming community.

Deprecating policy based data structures will deal much pain to some
competitors because problems in which it's possible to use pbds instead of
custom balanced binary trees occur quite often and so now we'll have to
implement bbst instead of using something out of the box.

Not sure if you would consider this usage case as something "serious", but
well, I was asked, so I answered.

Regards,
Oleksandr Kulkov

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

[Alexander Kulkov]

I hoped it would attach to
https://gcc.gnu.org/ml/libstdc++/2019-05/msg00107.html but it didn't happen
:(

ср, 10 июл. 2019 г. в 01:39, Alexander Kulkov <adamant.pwn@gmail.com>:

> Hi there! I hope, this message will go to where it's expected to go, since
> I'm not really familiar with e-mail threads.
>
> I was the one who brought
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806 issue about
> sub-optimal implementation of split function in pbds. The reason why I did
> so is clearly described on this comment:
> https://codeforces.com/blog/entry/10355?#comment-157883
>
> So, a bit of story and context. Five years ago at codeforces.com
> (competitive programming website) someone eventually pointed out that there
> is order-statistics tree in SGI library. It turned out to be very useful in
> competitions since it is quite common type of queries to count number of
> elements less than k in set and unfortunately regular std::set doesn't
> provide such possibility although it would be extremely useful in
> competitions.
>
> I made two posts about pbds on codeforces to introduce them to community:
> https://codeforces.com/blog/entry/11080 and
> https://codeforces.com/blog/entry/13279. First one introduces structures
> in general and second one describes how to modify them so they support
> custom queries. Second one was not quite as popular, perhaps because it's
> not much easier to comprehend and remember concept than simply write
> something like cartesian tree on live contest. But the first one is pretty
> much alive, most recent comment was only 8 days ago.
>
> There was also another post (https://codeforces.com/blog/entry/60737)
> considering hash_map from pb_ds as a replacement for unordered_map since
> hash_map clearly outperform unordered_map. This one is also quite popular
> and well-known in competitive programming community.
>
> So speaking about "Do you actually use these containers?" I would say that
> I often use tree_order_statistics_node_update in competitions, and in
> general specifically tree_order_statistics_node_update and hash_map are
> pretty popular in competitive programming community.
>
> Deprecating policy based data structures will deal much pain to some
> competitors because problems in which it's possible to use pbds instead of
> custom balanced binary trees occur quite often and so now we'll have to
> implement bbst instead of using something out of the box.
>
> Not sure if you would consider this usage case as something "serious", but
> well, I was asked, so I answered.
>
> Regards,
> Oleksandr Kulkov
>

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

[Jonathan Wakely]

On Tue, 9 Jul 2019 at 23:44, Alexander Kulkov wrote:
>
> I hoped it would attach to
> https://gcc.gnu.org/ml/libstdc++/2019-05/msg00107.html but it didn't happen
> :(

The links to other messages in a thread only work within the same
month, so you'll never get links between archived posts sent in
different months.

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

[Jonathan Wakely]

Sorry for the late reply that wasn't "tomorrow".

On Tue, 9 Jul 2019 at 23:40, Alexander Kulkov wrote:
>
> Hi there! I hope, this message will go to where it's expected to go, since
> I'm not really familiar with e-mail threads.
>
> I was the one who brought https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
> issue about sub-optimal implementation of split function in pbds. The
> reason why I did so is clearly described on this comment:
> https://codeforces.com/blog/entry/10355?#comment-157883
>
> So, a bit of story and context. Five years ago at codeforces.com
> (competitive programming website) someone eventually pointed out that there
> is order-statistics tree in SGI library. It turned out to be very useful in
> competitions since it is quite common type of queries to count number of
> elements less than k in set and unfortunately regular std::set doesn't
> provide such possibility although it would be extremely useful in
> competitions.
>
> I made two posts about pbds on codeforces to introduce them to community:
> https://codeforces.com/blog/entry/11080 and
> https://codeforces.com/blog/entry/13279. First one introduces structures in
> general and second one describes how to modify them so they support custom
> queries. Second one was not quite as popular, perhaps because it's not much
> easier to comprehend and remember concept than simply write something like
> cartesian tree on live contest. But the first one is pretty much alive,
> most recent comment was only 8 days ago.
>
> There was also another post (https://codeforces.com/blog/entry/60737)
> considering hash_map from pb_ds as a replacement for unordered_map since
> hash_map clearly outperform unordered_map. This one is also quite popular
> and well-known in competitive programming community.
>
> So speaking about "Do you actually use these containers?" I would say that
> I often use tree_order_statistics_node_update in competitions, and in
> general specifically tree_order_statistics_node_update and hash_map are
> pretty popular in competitive programming community.
>
> Deprecating policy based data structures will deal much pain to some
> competitors because problems in which it's possible to use pbds instead of
> custom balanced binary trees occur quite often and so now we'll have to
> implement bbst instead of using something out of the box.
>
> Not sure if you would consider this usage case as something "serious", but
> well, I was asked, so I answered.

Thanks for responding!

I don't really care about this use case, sorry. If the programming
competition community were providing fixes or improvements for this
code I might be more inclined to keep supported it, but it seems like
we're just carrying around a huge chunk of code because it saves
people some time in some competitions. Presumably the competition code
is not reused, so there's no backwards compatibility issue here
either.

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

[Alexander Kulkov]

Sounds fair to me. Well, I personally might be interested in providing
fixes and improvements for the code. I might even try to find some other
people in community to contribute.

PBDS is very well-thought library which I admired since the moment I saw
it, and the possibility that it may completely go to waste kind of
disappoints me, so I might put considerable effort to save it if that's
possible. The major issue, though, is that I don't really know even how to
start since I'm completely new to libstdc++ and have little experience with
such huge projects. Any help and/or advice here in how I may contribute
would be much appreciated.

вт, 23 июл. 2019 г. в 19:21, Jonathan Wakely <jwakely.gcc@gmail.com>:

> Sorry for the late reply that wasn't "tomorrow".
>
> On Tue, 9 Jul 2019 at 23:40, Alexander Kulkov wrote:
> >
> > Hi there! I hope, this message will go to where it's expected to go,
> since
> > I'm not really familiar with e-mail threads.
> >
> > I was the one who brought
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
> > issue about sub-optimal implementation of split function in pbds. The
> > reason why I did so is clearly described on this comment:
> > https://codeforces.com/blog/entry/10355?#comment-157883
> >
> > So, a bit of story and context. Five years ago at codeforces.com
> > (competitive programming website) someone eventually pointed out that
> there
> > is order-statistics tree in SGI library. It turned out to be very useful
> in
> > competitions since it is quite common type of queries to count number of
> > elements less than k in set and unfortunately regular std::set doesn't
> > provide such possibility although it would be extremely useful in
> > competitions.
> >
> > I made two posts about pbds on codeforces to introduce them to community:
> > https://codeforces.com/blog/entry/11080 and
> > https://codeforces.com/blog/entry/13279. First one introduces
> structures in
> > general and second one describes how to modify them so they support
> custom
> > queries. Second one was not quite as popular, perhaps because it's not
> much
> > easier to comprehend and remember concept than simply write something
> like
> > cartesian tree on live contest. But the first one is pretty much alive,
> > most recent comment was only 8 days ago.
> >
> > There was also another post (https://codeforces.com/blog/entry/60737)
> > considering hash_map from pb_ds as a replacement for unordered_map since
> > hash_map clearly outperform unordered_map. This one is also quite popular
> > and well-known in competitive programming community.
> >
> > So speaking about "Do you actually use these containers?" I would say
> that
> > I often use tree_order_statistics_node_update in competitions, and in
> > general specifically tree_order_statistics_node_update and hash_map are
> > pretty popular in competitive programming community.
> >
> > Deprecating policy based data structures will deal much pain to some
> > competitors because problems in which it's possible to use pbds instead
> of
> > custom balanced binary trees occur quite often and so now we'll have to
> > implement bbst instead of using something out of the box.
> >
> > Not sure if you would consider this usage case as something "serious",
> but
> > well, I was asked, so I answered.
>
> Thanks for responding!
>
> I don't really care about this use case, sorry. If the programming
> competition community were providing fixes or improvements for this
> code I might be more inclined to keep supported it, but it seems like
> we're just carrying around a huge chunk of code because it saves
> people some time in some competitions. Presumably the competition code
> is not reused, so there's no backwards compatibility issue here
> either.
>

Re: RFC: Deprecate libstdc++ Policy-Based Data Structures

[Tadeus Prastowo]

Hi,

Knowing that Alex has stepped forward, I am interested in helping out
in this matter as well if you think that will help.  My experience in
maintaining a C++ library can be seen at
https://savannah.nongnu.org/projects/tice

-- 
Best regards,
Tadeus

On Tue, Jul 23, 2019 at 6:50 PM Alexander Kulkov <adamant.pwn@gmail.com> wrote:
>
> Sounds fair to me. Well, I personally might be interested in providing
> fixes and improvements for the code. I might even try to find some other
> people in community to contribute.
>
> PBDS is very well-thought library which I admired since the moment I saw
> it, and the possibility that it may completely go to waste kind of
> disappoints me, so I might put considerable effort to save it if that's
> possible. The major issue, though, is that I don't really know even how to
> start since I'm completely new to libstdc++ and have little experience with
> such huge projects. Any help and/or advice here in how I may contribute
> would be much appreciated.
>
> вт, 23 июл. 2019 г. в 19:21, Jonathan Wakely <jwakely.gcc@gmail.com>:
>
> > Sorry for the late reply that wasn't "tomorrow".
> >
> > On Tue, 9 Jul 2019 at 23:40, Alexander Kulkov wrote:
> > >
> > > Hi there! I hope, this message will go to where it's expected to go,
> > since
> > > I'm not really familiar with e-mail threads.
> > >
> > > I was the one who brought
> > https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81806
> > > issue about sub-optimal implementation of split function in pbds. The
> > > reason why I did so is clearly described on this comment:
> > > https://codeforces.com/blog/entry/10355?#comment-157883
> > >
> > > So, a bit of story and context. Five years ago at codeforces.com
> > > (competitive programming website) someone eventually pointed out that
> > there
> > > is order-statistics tree in SGI library. It turned out to be very useful
> > in
> > > competitions since it is quite common type of queries to count number of
> > > elements less than k in set and unfortunately regular std::set doesn't
> > > provide such possibility although it would be extremely useful in
> > > competitions.
> > >
> > > I made two posts about pbds on codeforces to introduce them to community:
> > > https://codeforces.com/blog/entry/11080 and
> > > https://codeforces.com/blog/entry/13279. First one introduces
> > structures in
> > > general and second one describes how to modify them so they support
> > custom
> > > queries. Second one was not quite as popular, perhaps because it's not
> > much
> > > easier to comprehend and remember concept than simply write something
> > like
> > > cartesian tree on live contest. But the first one is pretty much alive,
> > > most recent comment was only 8 days ago.
> > >
> > > There was also another post (https://codeforces.com/blog/entry/60737)
> > > considering hash_map from pb_ds as a replacement for unordered_map since
> > > hash_map clearly outperform unordered_map. This one is also quite popular
> > > and well-known in competitive programming community.
> > >
> > > So speaking about "Do you actually use these containers?" I would say
> > that
> > > I often use tree_order_statistics_node_update in competitions, and in
> > > general specifically tree_order_statistics_node_update and hash_map are
> > > pretty popular in competitive programming community.
> > >
> > > Deprecating policy based data structures will deal much pain to some
> > > competitors because problems in which it's possible to use pbds instead
> > of
> > > custom balanced binary trees occur quite often and so now we'll have to
> > > implement bbst instead of using something out of the box.
> > >
> > > Not sure if you would consider this usage case as something "serious",
> > but
> > > well, I was asked, so I answered.
> >
> > Thanks for responding!
> >
> > I don't really care about this use case, sorry. If the programming
> > competition community were providing fixes or improvements for this
> > code I might be more inclined to keep supported it, but it seems like
> > we're just carrying around a huge chunk of code because it saves
> > people some time in some competitions. Presumably the competition code
> > is not reused, so there's no backwards compatibility issue here
> > either.
> >

RFC: Deprecate libstdc++ Policy-Based Data Structures

[Jonathan Wakely]

I'm including gcc@gcc.gnu.org here for visibility, but the discussion
really belongs on the libstdc++ list so please limit replies to there.

I'd like to discuss deprecating (and eventually removing) the
libstdc++-v3/include/ext/pb_ds extensions. For information on them see
https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

There has been exactly one (1) bug report for them in the past seven
years since the code stabilized (i.e. when Benjamin stopped working on
them). The bug reporter and the author of the fix have both confirmed
they don't use them for anything "serious" that requires them to be
shipped as part of GCC (see PR 62045).

I can find no uses of them in https://codesearch.debian.net or
https://codesearch.isocpp.org/

They require occasional tweaking but many of the changes are just
touching comments. However, running the tests is very slow, see 
https://gcc.gnu.org/ml/libstdc++/2019-03/msg00012.html

I'd like to consider deprecating them, and then removing them from the
libstdc++ tree. There's no reason the code can't be moved to a
separate project on sourceware.org (and/or gitlab, github etc.) but I
don't think it needs to be maintained as part of libstdc++.