This is the mail archive of the
mailing list for the GCC project.
Re: [GSoC] Question about std::map
- From: Tobias Grosser <tobias at grosser dot es>
- To: Trevor Saunders <tsaunders at mozilla dot com>
- Cc: Roman Gareev <gareevroman at gmail dot com>, gcc at gcc dot gnu dot org, Mircea Namolaru <mircea dot namolaru at inria dot fr>
- Date: Mon, 07 Jul 2014 13:08:58 +0200
- Subject: Re: [GSoC] Question about std::map
- Authentication-results: sourceware.org; auth=none
- References: <CABGF_gfEPTkYLxg74bykZasx6TTRMtWRTQRYWkc4B7g=Ex84fg at mail dot gmail dot com> <53B5987B dot 4060306 at grosser dot es> <20140704021609 dot GA30392 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com> <53B65E57 dot 8040508 at grosser dot es> <20140704220338 dot GC3933 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com>
On 05/07/2014 00:03, Trevor Saunders wrote:
On Fri, Jul 04, 2014 at 09:57:11AM +0200, Tobias Grosser wrote:
On 04/07/2014 04:16, Trevor Saunders wrote:
On Thu, Jul 03, 2014 at 07:52:59PM +0200, Tobias Grosser wrote:
On 03/07/2014 19:23, Roman Gareev wrote:
Dear gcc contributors,
could you please answer a few questions about std::map? Does gcc have
a policy that forbids using of map in the source code of gcc? Can this
using create a new installation dependency, which requires libstdc++?
I would be very grateful for your comments.
This suggests that using std::map is allowed. Running "grep 'std::' *"
on gcc, we only find a couple of std::make_pair, std::min and std::max
calls, but I don't see why we should not use std::map. I would say go for it
if there are no vetos. It seems to be the right tool for what you are aiming
for and certainly makes the code a lot more readable.
I'm certainly not opposed to using the stl when it makes sense, and
reinventing our own stl has a fairly high cost. However I think the
question of if you should use std::map is a complicated one. First
remember std::map is a tree, not a hash table, and consider which
performance characteristic you want. Also remember the stl in some
cases trades off possible optimizations to be more generic, if you
implement your own version of something you can say ban arrays larger
than 2^32 and thereby save a bit of space. When you use the stl you
also need to make sure you don't call things that can throw exceptions
since gcc is built with -fno-exceptions and generally isn't exception
I think there are some stl things you should basically always prefer
e.g. std::swap, there are some things you should think about before
using, and some things that are best avoided. Personally I think you
should favor hash tables to std::map most of the time because of there
generally better performance.
btw if you have specific gripes about the stlish bits gcc already has
I'd like to hear them.
thanks for the feedback. You seem to have a good idea for which use cases a
std::map is possible. Maybe I can invite you to a patch review currently
happening on firstname.lastname@example.org (Roman, we should do this kind of stuff on
gcc-patches@ I suppose) under the title "[GSoC] generation of GCC expression
trees from isl ast expressions". Feel free to ignore most of the code. The
question I am unsure about is the use of ast_isl_index_hasher() and related
function, which takes 105 lines of code and alomost the same functionality
could be implemented by a one-line use of std::map<>. The maps generated are
have you tried the hash_map class I introduced a couple days ago? (maybe
we should teach its generic machinary about strings, but it should
already be better than hash_table for your purpose).
No. We did not yet. Thanks for pointing it out.
> One thing that
confuses me is that you seem to be mapping from ast node to ast node,
but you do the actual mapping with strings, why is that needed?
Actually it is a mapping from isl_id to tree, but there seems to be some
additional information mixed in. All this is hidden in the current hash
map code and makes this rather confusing.
I think the best is to use the std::map to make the code work with the
simplest interface possible. After everything in place we can then test
if the move to hash_map gives any performance benefits.
commonly small and I doubt this is in the performance critical path. I feel
very worried about adding so much bloat? What would you suggest.
yeah, that code kind of made my eyes glaze over on the other hand your
talking about going from average constant time to average log time,
which is the sort of thing I'm pretty hesitent to say is a great idea.
The number of elements in these maps is most likely between 3-10.
Its too bad unordered_map isn't an option.
Thanks again for your help!