Repository: logging-log4j2 Updated Branches: refs/heads/master d16716a58 -> c05f75b43
LOG4J2-1010 LOG4J2-1447 optimization for merging two non-empty SortedArrayStringMap instances (e.g. injecting context data when logger has properties configured) Project: http://git-wip-us.apache.org/repos/asf/logging-log4j2/repo Commit: http://git-wip-us.apache.org/repos/asf/logging-log4j2/commit/c05f75b4 Tree: http://git-wip-us.apache.org/repos/asf/logging-log4j2/tree/c05f75b4 Diff: http://git-wip-us.apache.org/repos/asf/logging-log4j2/diff/c05f75b4 Branch: refs/heads/master Commit: c05f75b43df42d9aa9adc9e805f084b750f0c1dc Parents: d16716a Author: rpopma <[email protected]> Authored: Sat Sep 24 22:43:35 2016 +0900 Committer: rpopma <[email protected]> Committed: Sat Sep 24 22:43:35 2016 +0900 ---------------------------------------------------------------------- .../log4j/util/SortedArrayStringMap.java | 57 +++- .../log4j/util/SortedArrayStringMapTest.java | 257 +++++++++++++++++++ 2 files changed, 311 insertions(+), 3 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/logging-log4j2/blob/c05f75b4/log4j-api/src/main/java/org/apache/logging/log4j/util/SortedArrayStringMap.java ---------------------------------------------------------------------- diff --git a/log4j-api/src/main/java/org/apache/logging/log4j/util/SortedArrayStringMap.java b/log4j-api/src/main/java/org/apache/logging/log4j/util/SortedArrayStringMap.java index 479bda2..07f8f0b 100644 --- a/log4j-api/src/main/java/org/apache/logging/log4j/util/SortedArrayStringMap.java +++ b/log4j-api/src/main/java/org/apache/logging/log4j/util/SortedArrayStringMap.java @@ -215,14 +215,18 @@ public class SortedArrayStringMap implements StringMap { @Override public void putAll(final ReadOnlyStringMap source) { - if (source == this) { + if (source == this || source.isEmpty()) { // throw NPE if null return; // this.putAll(this) does not modify this collection } assertNotFrozen(); assertNoConcurrentModification(); - if (source instanceof SortedArrayStringMap && this.size == 0) { - initFrom0((SortedArrayStringMap) source); + if (source instanceof SortedArrayStringMap) { + if (this.size == 0) { + initFrom0((SortedArrayStringMap) source); + } else { + merge((SortedArrayStringMap) source); + } } else if (source != null) { source.forEach(PUT_ALL, this); } @@ -240,6 +244,53 @@ public class SortedArrayStringMap implements StringMap { threshold = other.threshold; } + private void merge(final SortedArrayStringMap other) { + final String[] myKeys = keys; + final Object[] myVals = values; + final int newSize = other.size + this.size; + threshold = ceilingNextPowerOfTwo(newSize); + if (keys.length < threshold) { + keys = new String[threshold]; + values = new Object[threshold]; + } + // move largest collection to the beginning of this data structure, smallest to the end + boolean overwrite = true; + if (other.size() > size()) { + // move original key-values to end + System.arraycopy(myKeys, 0, keys, other.size, this.size); + System.arraycopy(myVals, 0, values, other.size, this.size); + + // insert additional key-value pairs at the beginning + System.arraycopy(other.keys, 0, keys, 0, other.size); + System.arraycopy(other.values, 0, values, 0, other.size); + size = other.size; + + // loop over original keys and insert (drop values for same key) + overwrite = false; + } else { + System.arraycopy(myKeys, 0, keys, 0, this.size); + System.arraycopy(myVals, 0, values, 0, this.size); + + // move additional key-value pairs to end + System.arraycopy(other.keys, 0, keys, this.size, other.size); + System.arraycopy(other.values, 0, values, this.size, other.size); + + // new values are at the end, will be processed below. Overwrite is true. + } + for (int i = size; i < newSize; i++) { + final int index = indexOfKey(keys[i]); + if (index < 0) { // key does not exist + insertAt(~index, keys[i], values[i]); + } else if (overwrite) { // existing key: only overwrite when looping over the new values + keys[index] = keys[i]; + values[index] = values[i]; + } + } + // prevent memory leak: null out references + Arrays.fill(keys, size, newSize, null); + Arrays.fill(values, size, newSize, null); + } + private void ensureCapacity() { if (size >= threshold) { resize(threshold * 2); http://git-wip-us.apache.org/repos/asf/logging-log4j2/blob/c05f75b4/log4j-api/src/test/java/org/apache/logging/log4j/util/SortedArrayStringMapTest.java ---------------------------------------------------------------------- diff --git a/log4j-api/src/test/java/org/apache/logging/log4j/util/SortedArrayStringMapTest.java b/log4j-api/src/test/java/org/apache/logging/log4j/util/SortedArrayStringMapTest.java index 42bfce7..f4f0710 100644 --- a/log4j-api/src/test/java/org/apache/logging/log4j/util/SortedArrayStringMapTest.java +++ b/log4j-api/src/test/java/org/apache/logging/log4j/util/SortedArrayStringMapTest.java @@ -106,6 +106,200 @@ public class SortedArrayStringMapTest { } @Test + public void testPutAll_overwritesSameKeys2() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + original.putValue("c", "cORIG"); + original.putValue("d", "dORIG"); + original.putValue("e", "eORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue("1", "11"); + other.putValue("2", "22"); + other.putValue("a", "aa"); + other.putValue("c", "cc"); + original.putAll(other); + + assertEquals("size after put other", 7, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("cc", original.getValue("c")); + assertEquals("dORIG", original.getValue("d")); + assertEquals("eORIG", original.getValue("e")); + assertEquals("11", original.getValue("1")); + assertEquals("22", original.getValue("2")); + } + + @Test + public void testPutAll_nullKeyInLargeOriginal() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue(null, "nullORIG"); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + original.putValue("c", "cORIG"); + original.putValue("d", "dORIG"); + original.putValue("e", "eORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue("1", "11"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 7, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("cORIG", original.getValue("c")); + assertEquals("dORIG", original.getValue("d")); + assertEquals("eORIG", original.getValue("e")); + assertEquals("11", original.getValue("1")); + assertEquals("nullORIG", original.getValue(null)); + } + + @Test + public void testPutAll_nullKeyInSmallOriginal() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue(null, "nullORIG"); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue("1", "11"); + other.putValue("2", "22"); + other.putValue("3", "33"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 6, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("11", original.getValue("1")); + assertEquals("22", original.getValue("2")); + assertEquals("33", original.getValue("3")); + assertEquals("nullORIG", original.getValue(null)); + } + + @Test + public void testPutAll_nullKeyInSmallAdditional() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + original.putValue("c", "cORIG"); + original.putValue("d", "dORIG"); + original.putValue("e", "eORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue(null, "nullNEW"); + other.putValue("1", "11"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 7, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("cORIG", original.getValue("c")); + assertEquals("dORIG", original.getValue("d")); + assertEquals("eORIG", original.getValue("e")); + assertEquals("11", original.getValue("1")); + assertEquals("nullNEW", original.getValue(null)); + } + + @Test + public void testPutAll_nullKeyInLargeAdditional() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue(null, "nullNEW"); + other.putValue("1", "11"); + other.putValue("2", "22"); + other.putValue("3", "33"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 6, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("11", original.getValue("1")); + assertEquals("22", original.getValue("2")); + assertEquals("33", original.getValue("3")); + assertEquals("nullNEW", original.getValue(null)); + } + + @Test + public void testPutAll_nullKeyInBoth_LargeOriginal() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue(null, "nullORIG"); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + original.putValue("c", "cORIG"); + original.putValue("d", "dORIG"); + original.putValue("e", "eORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue(null, "nullNEW"); + other.putValue("1", "11"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 7, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("cORIG", original.getValue("c")); + assertEquals("dORIG", original.getValue("d")); + assertEquals("eORIG", original.getValue("e")); + assertEquals("11", original.getValue("1")); + assertEquals("nullNEW", original.getValue(null)); + } + + @Test + public void testPutAll_nullKeyInBoth_SmallOriginal() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue(null, "nullORIG"); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue(null, "nullNEW"); + other.putValue("1", "11"); + other.putValue("2", "22"); + other.putValue("3", "33"); + other.putValue("a", "aa"); + original.putAll(other); + + assertEquals("size after put other", 6, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("11", original.getValue("1")); + assertEquals("22", original.getValue("2")); + assertEquals("33", original.getValue("3")); + assertEquals("nullNEW", original.getValue(null)); + } + + @Test + public void testPutAll_overwritesSameKeys1() throws Exception { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue("a", "aORIG"); + original.putValue("b", "bORIG"); + original.putValue("c", "cORIG"); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue("1", "11"); + other.putValue("2", "22"); + other.putValue("a", "aa"); + other.putValue("c", "cc"); + original.putAll(other); + + assertEquals("size after put other", 5, original.size()); + assertEquals("aa", original.getValue("a")); + assertEquals("bORIG", original.getValue("b")); + assertEquals("cc", original.getValue("c")); + assertEquals("11", original.getValue("1")); + assertEquals("22", original.getValue("2")); + } + + @Test public void testEquals() { final SortedArrayStringMap original = new SortedArrayStringMap(); original.putValue("a", "avalue"); @@ -185,6 +379,69 @@ public class SortedArrayStringMapTest { } @Test + public void testPutAll_sizePowerOfTwo() { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue("a", "aaa"); + original.putValue("b", "bbb"); + original.putValue("c", "ccc"); + original.putValue("d", "ddd"); + assertEquals("size", 4, original.size()); + + // add empty context data + original.putAll(new SortedArrayStringMap()); + assertEquals("size after put empty", 4, original.size()); + assertEquals("aaa", original.getValue("a")); + assertEquals("bbb", original.getValue("b")); + assertEquals("ccc", original.getValue("c")); + assertEquals("ddd", original.getValue("d")); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + other.putValue("1", "111"); + other.putValue("2", "222"); + other.putValue("3", "333"); + other.putValue("4", "444"); + original.putAll(other); + + assertEquals("size after put other", 8, original.size()); + assertEquals("aaa", original.getValue("a")); + assertEquals("bbb", original.getValue("b")); + assertEquals("ccc", original.getValue("c")); + assertEquals("ddd", original.getValue("d")); + assertEquals("111", original.getValue("1")); + assertEquals("222", original.getValue("2")); + assertEquals("333", original.getValue("3")); + assertEquals("444", original.getValue("4")); + } + + @Test + public void testPutAll_largeAddition() { + final SortedArrayStringMap original = new SortedArrayStringMap(); + original.putValue(null, "nullVal"); + original.putValue("a", "aaa"); + original.putValue("b", "bbb"); + original.putValue("c", "ccc"); + original.putValue("d", "ddd"); + assertEquals("size", 5, original.size()); + + final SortedArrayStringMap other = new SortedArrayStringMap(); + for (int i = 0 ; i < 500; i++) { + other.putValue(String.valueOf(i), String.valueOf(i)); + } + other.putValue(null, "otherVal"); + original.putAll(other); + + assertEquals("size after put other", 505, original.size()); + assertEquals("otherVal", original.getValue(null)); + assertEquals("aaa", original.getValue("a")); + assertEquals("bbb", original.getValue("b")); + assertEquals("ccc", original.getValue("c")); + assertEquals("ddd", original.getValue("d")); + for (int i = 0 ; i < 500; i++) { + assertEquals(String.valueOf(i), original.getValue(String.valueOf(i))); + } + } + + @Test public void testPutAllSelfDoesNotModify() { final SortedArrayStringMap original = new SortedArrayStringMap(); original.putValue("a", "aaa");
