Salikh Zakirov wrote: > I have been looking to the string interning code in DRLVM recently. > ... > Now I am going to attempt optimization of java code by using > a customized weak hashmap implementation. > By using it, I will be able to create just one weak reference > to the interned string instead of current two, and to perform > just one hash lookup instead of two on interning new string.
So I did it. I have taken java.lang.WeakHashMap, trimmed all the irrelevant code, and implemented intern() method, which returns the key if the string is already present in the table, and stores the string if it was not. The optimized implementation brings little advantage, here is the data (again, running Hello application on my laptop) baseline: avg 0.265 +/- 0.001 = 26.511 / 100, min 0.254, max 0.319 WeakHashMap: avg 0.270 +/- 0.001 = 26.952 / 100, min 0.258, max 0.310 customized: avg 0.268 +/- 0.001 = 26.815 / 100, min 0.256, max 0.309 Thus, the optimized java implementation of interned strings brings overhead down about 1%. The patch to implement customized InternMap, based on WeakHashMap code is attached. Is anyone reviewing patches? I think it is genarally more convenient to review patches sent to the list, because it is easy to hit "reply" and put the comments inline to the particular code. (This practice is widely used in other mailing lists I am looking through, e.g. Git) I will file a JIRA with patches anyway to make sure the patch is not lost. (in hope that it will be eventually applied) -- Salikh Zakirov, Intel Middleware Products Division
>From 836b5a8c508f42169e81a3d88cb5f41b785a7215 Mon Sep 17 00:00:00 2001 From: Salikh Zakirov <[EMAIL PROTECTED]> Date: Wed, 26 Jul 2006 20:45:49 +0400 Subject: [PATCH] optimized weak map implementation: InternMap WeakHashMap trimmed down to delete the functionality unused by string pool. The only features left are - weak references to keys - regular polling and cleaning - hashihg Instead of get() and put() methods, the only method intern() is used, which returns the interned key value if the lookup is successful, or interns the passed in key value otherwise. --- .../org/apache/harmony/kernel/vm/InternMap.java | 145 +++++++++++++++++++++++ .../javasrc/org/apache/harmony/kernel/vm/VM.java | 20 --- 2 files changed, 148 insertions(+), 17 deletions(-) diff --git a/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/InternMap.java b/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/InternMap.java new file mode 100755 index 0000000..e2001bd --- /dev/null +++ b/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/InternMap.java @@ -0,0 +1,145 @@ +/* Copyright 1998, 2005 The Apache Software Foundation or its licensors, as applicable + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.harmony.kernel.vm; + +import java.lang.ref.ReferenceQueue; +import java.lang.ref.WeakReference; + +/** + * Implements weak hash map specialized for storing interned string pool. + * @see java.util.WeakHashMap + * @see WeakReference + */ +public class InternMap { + + private final ReferenceQueue referenceQueue; + + int elementCount; + + Entry[] elementData; + + private final int loadFactor; + + private int threshold; + + //Simple utility method to isolate unchecked cast for array creation + private static Entry[] newEntryArray(int size) { + return new Entry[size]; + } + + private static final class Entry extends WeakReference { + int hash; + Entry next; + Entry(String key, ReferenceQueue queue) { + super(key, queue); + hash = key.hashCode(); + } + } + + public InternMap(int capacity) { + if (capacity >= 0) { + elementCount = 0; + elementData = newEntryArray(capacity == 0 ? 1 : capacity); + loadFactor = 7500; // Default load factor of 0.75 + computeMaxSize(); + referenceQueue = new ReferenceQueue(); + } else { + throw new IllegalArgumentException(); + } + } + + private void computeMaxSize() { + threshold = (int) ((long) elementData.length * loadFactor / 10000); + } + + void poll() { + Entry toRemove; + while ((toRemove = (Entry)referenceQueue.poll()) != null) { + removeEntry(toRemove); + } + } + + void removeEntry(Entry toRemove) { + Entry entry, last = null; + int index = (toRemove.hash & 0x7FFFFFFF) % elementData.length; + entry = elementData[index]; + // Ignore queued entries which cannot be found, the user could + // have removed them before they were queued, i.e. using clear() + while (entry != null) { + if (toRemove == entry) { + if (last == null) { + elementData[index] = entry.next; + } else { + last.next = entry.next; + } + elementCount--; + break; + } + last = entry; + entry = entry.next; + } + } + + public String intern(String key) { + int index = 0; + Entry entry; + String interned = null; + if (key == null) + return null; + index = (key.hashCode() & 0x7FFFFFFF) % elementData.length; + entry = elementData[index]; + while (entry != null && !key.equals(interned = (String)entry.get())) { + entry = entry.next; + } + + // if we found the entry, return it + if (entry != null) { + return interned; + } + + // no interned string found, put a new entry for it + if (++elementCount > threshold) { + rehash(); + index = (key.hashCode() & 0x7FFFFFFF) % elementData.length; + } + entry = new Entry(key, referenceQueue); + entry.next = elementData[index]; + elementData[index] = entry; + return key; + } + + private void rehash() { + poll(); + int length = elementData.length << 1; + if (length == 0) { + length = 1; + } + Entry[] newData = newEntryArray(length); + for (int i = 0; i < elementData.length; i++) { + Entry entry = elementData[i]; + while (entry != null) { + int index = (entry.hash & 0x7FFFFFFF) % length; + Entry next = entry.next; + entry.next = newData[index]; + newData[index] = entry; + entry = next; + } + } + elementData = newData; + computeMaxSize(); + } +} + diff --git a/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/VM.java b/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/VM.java index 0f47529..dd3a10c 100755 --- a/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/VM.java +++ b/vm/vmcore/src/kernel_classes/javasrc/org/apache/harmony/kernel/vm/VM.java @@ -133,27 +133,13 @@ public final class VM { // in this function or functions called // from here - // OPTIMIZEME: two weak reference object per interned string - // OPTIMIZEME: change get() put() to get_or_update() - WeakReference ref = internedStrings.get(s); - String interned = null; - if (ref != null) { - interned = (String)ref.get(); - } - if (interned != null) { - return interned; - } else { - // if the string was never interned, or was reclaimed, - // then store the passed in string reference - internedStrings.put(s,new WeakReference(s)); - return s; - } + return internedStrings.intern(s); } - private static WeakHashMap<String,WeakReference> internedStrings; + private static InternMap internedStrings; static { // initialize the storage for interned strings - internedStrings = new WeakHashMap(32768); + internedStrings = new InternMap(32768); } } -- 1.4.1.g4b86
--------------------------------------------------------------------- Terms of use : http://incubator.apache.org/harmony/mailing.html To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
