Plan for ordering in our hash-based collections

google / guava

Google core libraries for Java

Apache License 2.0

50.03k stars 10.86k forks source link

Plan for ordering in our hash-based collections #2068

Open cpovirk opened 9 years ago

cpovirk commented 9 years ago

We may have already come up with one. If so, I'm sure someone can point me to it.

Will we change types like HashMultimap to maintain order (basically making it LinkedHashMultimap)? This used to be extremely appealing. Now that we're looking more at Android users, we might prioritize memory usage. If so, the extra pointers required are less appealing.
Would we consider a "nudge" approach in which MultimapBuilder and the forthcoming BiMapBuilder (which may supplant public classes like HashMultimap in time) treat hashKeys as a request for linkedHashKeys and provide unorderedHashKeys for users who really want to save memory?

swankjesse commented 9 years ago

I don't think the extra links will make a meaningful difference on Android users. The bulk of the RAM in an Android app is used by high-resolution images!

kevinb9n commented 9 years ago

Yeah, I get the sense that we care more about minimizing garbage allocation that reducing footprint.

On Tue, Jun 2, 2015 at 10:26 AM, Jesse Wilson notifications@github.com wrote:

I don't think the extra links will make a meaningful difference on Android users. The bulk of the RAM in an Android app is used by high-resolution images!

— Reply to this email directly or view it on GitHub https://github.com/google/guava/issues/2068#issuecomment-108023481.

Kevin Bourrillion | Java Librarian | Google, Inc. | kevinb@google.com

lowasser commented 9 years ago

My understanding was always that it was number of distinct objects, rather than their size?

On Tue, Jun 2, 2015 at 10:54 AM kevinb9n notifications@github.com wrote:

Yeah, I get the sense that we care more about minimizing garbage allocation that reducing footprint.

On Tue, Jun 2, 2015 at 10:26 AM, Jesse Wilson notifications@github.com wrote:

I don't think the extra links will make a meaningful difference on Android users. The bulk of the RAM in an Android app is used by high-resolution images!

— Reply to this email directly or view it on GitHub https://github.com/google/guava/issues/2068#issuecomment-108023481.

Kevin Bourrillion | Java Librarian | Google, Inc. | kevinb@google.com

— Reply to this email directly or view it on GitHub https://github.com/google/guava/issues/2068#issuecomment-108030561.

swankjesse commented 9 years ago

The number of objects allocated in LinkedHashMap is the same as in HashMap. Not sure about LinkedHashMultimap.

lowasser commented 9 years ago

IIRC, LinkedHashMultimap allocates at most as many objects as HashMultimap, and possibly fewer, due to the deeply customized implementation.

cpovirk commented 5 years ago

It looks like we abandoned the HashMultimap changes (CL 90428283) after hitting some trouble with GWT serialization. If we were motivated, we could pick that back up when we drop GWT-RPC support.

On the other hand, we're at least slightly steering people away from HashMultimap and the other public Multimap implementations and toward MultimapBuilder, so users might not even benefit from changes to MultimapBuilder. Or we could make MultimapBuilder return a HashMultimap in case of hashKeys()+hashValues() and/or linkedHashKeys()/linkedHashValues()....

But I'm unsure how much of a priority this is for us.

cpovirk commented 5 years ago

(Making MultimapBuilder return a HashMultimap might also make MultimapBuilder a worse choice for Proguard users, since any use of MultimapBuilder would likely retain HashMultimap.)