Re: [PATCH] Simplification of TreeMap

[Michael Kuhlmann]

Hi Sergey and Sergey ;),

that's totally correct! Serialization really is a beast sometimes, you
have to take care that instances that have been serialized even with
Java 1.2 still get deserialized correctly in the current version.

So it's not sufficient to only look at the constructors when the class
is Serializable. In the case of TreeMap, the only solutions I see are
either making 'comparator' mutable and setting it in readObject(), or
again always check for null values when accessing it - which would make
your idea rather useless. As Martin already mentioned, "if it's not
broken, don't fix it" - either option is not worth the change.

What would make sense is to remove valEquals() in favor of
Objects::equals, so at least a minor patch would remain. ;)

-Michael


Am 05.09.2018 um 21:22 schrieb Sergey:
> Hi Sergey,
> 
> Michael might correct me if I’ve missed something, but 
> problem with your test case is that you’re serializing already 
> patched version. That makes sense if you want to test current 
> behavior. However the case you truly want to test is how your
> patched TreeMap deserializes pre-patched TreeMaps.
> 
> What you have currently just tests if patched map could be
> deserialized without any problems.
> 
> Cheers,
> su -
> 
> On Wed, 5 Sep 2018 at 20:30, Сергей Цыпанов  > wrote:
> 
> Hi Michael,
> 
> thanks for pointing out this serialization concern, I didn't think
> about it at all.
> 
> I've wrote a simple test for serialization of patched TreeMap and it
> works without errors for both no-args constructor and constructor
> with comparator:
> 
> public class TreeMapSerialization {
>     public static void main(String[] args) throws Exception {
>         TreeMap serialized = new
> TreeMap<>(Comparator.reverseOrder());
>         serialized.put(1, "1");
>         serialized.put(2, "2");
> 
>         ByteArrayOutputStream baos = new ByteArrayOutputStream();
>         ObjectOutputStream oos = new ObjectOutputStream(baos);
> 
>         oos.writeObject(serialized);
>         oos.flush();
>         baos.flush();
>         oos.close();
>         baos.close();
> 
>         ByteArrayInputStream bais = new
> ByteArrayInputStream(baos.toByteArray());
>         ObjectInputStream ois = new ObjectInputStream(bais);
> 
>         TreeMap deserialized = (TreeMap String>) ois.readObject();
>         deserialized.put(3, "3");
> 
>         System.out.println(deserialized);
>     }
> }
> 
> 
> I hope I don't miss anything, so there shouldn't be any
> serialization issues.
> 
> Regards,
> Sergey Tsypanov
> 

Re: [PATCH] Simplification of TreeMap

[Sergey]

Hi Sergey,

Michael might correct me if I’ve missed something, but
problem with your test case is that you’re serializing already
patched version. That makes sense if you want to test current
behavior. However the case you truly want to test is how your
patched TreeMap deserializes pre-patched TreeMaps.

What you have currently just tests if patched map could be
deserialized without any problems.

Cheers,
su -

On Wed, 5 Sep 2018 at 20:30, Сергей Цыпанов 
wrote:

> Hi Michael,
>
> thanks for pointing out this serialization concern, I didn't think about
> it at all.
>
> I've wrote a simple test for serialization of patched TreeMap and it works
> without errors for both no-args constructor and constructor with comparator:
>
> public class TreeMapSerialization {
> public static void main(String[] args) throws Exception {
> TreeMap serialized = new
> TreeMap<>(Comparator.reverseOrder());
> serialized.put(1, "1");
> serialized.put(2, "2");
>
> ByteArrayOutputStream baos = new ByteArrayOutputStream();
> ObjectOutputStream oos = new ObjectOutputStream(baos);
>
> oos.writeObject(serialized);
> oos.flush();
> baos.flush();
> oos.close();
> baos.close();
>
> ByteArrayInputStream bais = new
> ByteArrayInputStream(baos.toByteArray());
> ObjectInputStream ois = new ObjectInputStream(bais);
>
> TreeMap deserialized = (TreeMap)
> ois.readObject();
> deserialized.put(3, "3");
>
> System.out.println(deserialized);
> }
> }
>
>
> I hope I don't miss anything, so there shouldn't be any serialization
> issues.
>
> Regards,
> Sergey Tsypanov
>

Re: [PATCH] Simplification of TreeMap

[Martin Buchholz]

Сергей, they say "If it ain't broke, don't fix it".  Your implementation is
indeed more maintainable, but TreeMap has been rather stable and is
unlikely to see much maintenance!  (unless value types makes it compelling).

One of many problems with serialization is that cross-version compatibility
is hard to test and so usually ends up untested.

On Wed, Sep 5, 2018 at 11:30 AM, Сергей Цыпанов 
wrote:

> Hi Michael,
>
> thanks for pointing out this serialization concern, I didn't think about
> it at all.
>
> I've wrote a simple test for serialization of patched TreeMap and it works
> without errors for both no-args constructor and constructor with comparator:
>
> public class TreeMapSerialization {
> public static void main(String[] args) throws Exception {
> TreeMap serialized = new TreeMap<>(Comparator.
> reverseOrder());
> serialized.put(1, "1");
> serialized.put(2, "2");
>
> ByteArrayOutputStream baos = new ByteArrayOutputStream();
> ObjectOutputStream oos = new ObjectOutputStream(baos);
>
> oos.writeObject(serialized);
> oos.flush();
> baos.flush();
> oos.close();
> baos.close();
>
> ByteArrayInputStream bais = new ByteArrayInputStream(baos.
> toByteArray());
> ObjectInputStream ois = new ObjectInputStream(bais);
>
> TreeMap deserialized = (TreeMap)
> ois.readObject();
> deserialized.put(3, "3");
>
> System.out.println(deserialized);
> }
> }
>
>
> I hope I don't miss anything, so there shouldn't be any serialization
> issues.
>
> Regards,
> Sergey Tsypanov
>

Re: [PATCH] Simplification of TreeMap

[Сергей Цыпанов]

Hi Michael,

thanks for pointing out this serialization concern, I didn't think about it at 
all.

I've wrote a simple test for serialization of patched TreeMap and it works 
without errors for both no-args constructor and constructor with comparator:

public class TreeMapSerialization {
public static void main(String[] args) throws Exception {
TreeMap serialized = new 
TreeMap<>(Comparator.reverseOrder());
serialized.put(1, "1");
serialized.put(2, "2");

ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);

oos.writeObject(serialized);
oos.flush();
baos.flush();
oos.close();
baos.close();

ByteArrayInputStream bais = new 
ByteArrayInputStream(baos.toByteArray());
ObjectInputStream ois = new ObjectInputStream(bais);

TreeMap deserialized = (TreeMap) 
ois.readObject();
deserialized.put(3, "3");

System.out.println(deserialized);
}
}


I hope I don't miss anything, so there shouldn't be any serialization issues.

Regards,
Sergey Tsypanov

Re: [PATCH] Simplification of TreeMap

[Michael Kuhlmann]

Hi Sergey,

I was also wondering why TreeMap doesn't just use a default comparator
and always checks for null instead.

The problem with your patch is that deserialized TreeMap instances which
were serialized from a previous version would still have the comparator
set to null, thus resulting in a NPE after your patch. And you can't
easily fix this because comparator is a final field.

Best,
Michael


On 04.09.2018 21:14, Сергей Цыпанов wrote:
> Hi,
> 
> currently (latest code of JDK 11) an instance of TreeMap created with no-arg 
> contructor has nullable comparator i.e. utilizes no comparator.
> 
> As it comes from the code, a TreeMap created with nullable comparator works 
> exactly as a TreeMap created with comparator provided by 
> Comparator.naturalOrder(). This is also explicitly specifid in Javadoc.
> 
> I propose to initialize default comparator of TreeMap with instance of 
> Comparator returned by Comparator.naturalOrder() instead of null.
> This allows to remove the code responsible for handling nullable comparator, 
> e. g. TreeMap::getEntryUsingComparator can be completely removed in favour of 
> TreeMap::getEntry.
> Similar simplification available for TreeMap::put, TreeMap::compare, 
> EntrySpliterator::getComparator.
> 
> I've prepared a patch for this.
> The patch contains both described major change and some tiny clean-ups e. g. 
> utilization of Objects::requireNonNull where appropriate and Objects::equals 
> instead of hand-written TreeMap::valEquals.
> 
> TreeMapTest is green after my changes.
> 
> Regards,
> Sergey Tsypanov
> 
> 

Re: [PATCH] Simplification of TreeMap

[Remi Forax]

Hi Sergey,
if think the code is as it is because it's faster to check for the null 
comparator and have an ad-hoc code for this special case than using 
Comparator.naturalOrder(),
obviously, it's not may be true anymore, so you should test that there is no 
perf regression when creating your patch.

regards,
Rémi

- Mail original -
> De: "Сергей Цыпанов" 
> À: "core-libs-dev" 
> Envoyé: Mardi 4 Septembre 2018 21:14:21
> Objet: [PATCH] Simplification of TreeMap

> Hi,
> 
> currently (latest code of JDK 11) an instance of TreeMap created with no-arg
> contructor has nullable comparator i.e. utilizes no comparator.
> 
> As it comes from the code, a TreeMap created with nullable comparator works
> exactly as a TreeMap created with comparator provided by
> Comparator.naturalOrder(). This is also explicitly specifid in Javadoc.
> 
> I propose to initialize default comparator of TreeMap with instance of
> Comparator returned by Comparator.naturalOrder() instead of null.
> This allows to remove the code responsible for handling nullable comparator, 
> e.
> g. TreeMap::getEntryUsingComparator can be completely removed in favour of
> TreeMap::getEntry.
> Similar simplification available for TreeMap::put, TreeMap::compare,
> EntrySpliterator::getComparator.
> 
> I've prepared a patch for this.
> The patch contains both described major change and some tiny clean-ups e. g.
> utilization of Objects::requireNonNull where appropriate and Objects::equals
> instead of hand-written TreeMap::valEquals.
> 
> TreeMapTest is green after my changes.
> 
> Regards,
> Sergey Tsypanov

[PATCH] Simplification of TreeMap

[Сергей Цыпанов]

Hi,

currently (latest code of JDK 11) an instance of TreeMap created with no-arg 
contructor has nullable comparator i.e. utilizes no comparator.

As it comes from the code, a TreeMap created with nullable comparator works 
exactly as a TreeMap created with comparator provided by 
Comparator.naturalOrder(). This is also explicitly specifid in Javadoc.

I propose to initialize default comparator of TreeMap with instance of 
Comparator returned by Comparator.naturalOrder() instead of null.
This allows to remove the code responsible for handling nullable comparator, e. 
g. TreeMap::getEntryUsingComparator can be completely removed in favour of 
TreeMap::getEntry.
Similar simplification available for TreeMap::put, TreeMap::compare, 
EntrySpliterator::getComparator.

I've prepared a patch for this.
The patch contains both described major change and some tiny clean-ups e. g. 
utilization of Objects::requireNonNull where appropriate and Objects::equals 
instead of hand-written TreeMap::valEquals.

TreeMapTest is green after my changes.

Regards,
Sergey Tsypanov


diff --git a/src/java.base/share/classes/java/util/TreeMap.java b/src/java.base/share/classes/java/util/TreeMap.java
--- a/src/java.base/share/classes/java/util/TreeMap.java
+++ b/src/java.base/share/classes/java/util/TreeMap.java
@@ -133,6 +133,11 @@
 private transient int modCount = 0;
 
 /**
+ * Comparator used by default.
+ */
+private static final Comparator DEFAULT_COMPARATOR = Comparator.naturalOrder();
+
+/**
  * Constructs a new, empty tree map, using the natural ordering of its
  * keys.  All keys inserted into the map must implement the {@link
  * Comparable} interface.  Furthermore, all such keys must be
@@ -145,7 +150,7 @@
  * {@code ClassCastException}.
  */
 public TreeMap() {
-comparator = null;
+comparator = DEFAULT_COMPARATOR;
 }
 
 /**
@@ -163,7 +168,7 @@
  *ordering} of the keys will be used.
  */
 public TreeMap(Comparator comparator) {
-this.comparator = comparator;
+this.comparator = comparator == null ? DEFAULT_COMPARATOR : comparator;
 }
 
 /**
@@ -181,7 +186,7 @@
  * @throws NullPointerException if the specified map is null
  */
 public TreeMap(Map m) {
-comparator = null;
+this();
 putAll(m);
 }
 
@@ -195,7 +200,8 @@
  * @throws NullPointerException if the specified map is null
  */
 public TreeMap(SortedMap m) {
-comparator = m.comparator();
+Comparator comparator = m.comparator();
+this.comparator = comparator == null ? DEFAULT_COMPARATOR : comparator;
 try {
 buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
 } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
@@ -246,7 +252,7 @@
  */
 public boolean containsValue(Object value) {
 for (Entry e = getFirstEntry(); e != null; e = successor(e))
-if (valEquals(value, e.value))
+if (Objects.equals(value, e.value))
 return true;
 return false;
 }
@@ -312,7 +318,7 @@
 int mapSize = map.size();
 if (size==0 && mapSize!=0 && map instanceof SortedMap) {
 Comparator c = ((SortedMap)map).comparator();
-if (c == comparator || (c != null && c.equals(comparator))) {
+if (Objects.equals(c, comparator)) {
 ++modCount;
 try {
 buildFromSorted(mapSize, map.entrySet().iterator(),
@@ -338,16 +344,14 @@
  * does not permit null keys
  */
 final Entry getEntry(Object key) {
-// Offload comparator-based version for sake of performance
-if (comparator != null)
-return getEntryUsingComparator(key);
-if (key == null)
+if (key == null && comparator == DEFAULT_COMPARATOR)
 throw new NullPointerException();
 @SuppressWarnings("unchecked")
-Comparable k = (Comparable) key;
+K k = (K) key;
+Comparator cpr = comparator;
 Entry p = root;
 while (p != null) {
-int cmp = k.compareTo(p.key);
+int cmp = cpr.compare(k, p.key);
 if (cmp < 0)
 p = p.left;
 else if (cmp > 0)
@@ -359,31 +363,6 @@
 }
 
 /**
- * Version of getEntry using comparator. Split off from getEntry
- * for performance. (This is not worth doing for most methods,
- * that are less dependent on comparator performance, but is
- * worthwhile here.)
- */
-final Entry getEntryUsingComparator(Object key) {
-@SuppressWarnings("unchecked")
-K k = (K) key;
-Comparator cpr = comparator;
-if (cpr != null) {
-Entry p = root;
-while (p != null) {
-int cmp = cpr.compare(k, p.key);
-if (cmp < 0)
-p = p.left;
-