Hi all,
In our work with H2 at the State and University Library of Denmark we
encountered a strange performance decrease when inserting a certain kind of
records into our H2 database. Digging into H2 with the VisualVM profiler I
discovered that whopping 89% of the running time was spent in
BitField.getLastSetBit()!
I think what triggered this was that the new records inserted (really
OAI-PMH harvested abstracts) where bigger than our usual stuff which in turn
triggered some new code paths in H2 (writing the blob content to an external
file?).
Anyways - I added a cache to BitField.getLastSetBit() which dropped the 89%
running time down below 0.1%. This in turn provided us with almost x2.2
overall performance boost when inserting these kind of records.
I also have a patch for the 1.0.79 series of H2 - if anyone is interested
please email me or ping me here.
--
Cheers,
Mikkel Kamstrup Erlandsen
Software Developer at
State and University Library of Denmark
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "H2
Database" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/h2-database?hl=en
-~----------~----~----~----~------~----~------~--~---
Index: src/main/org/h2/util/BitField.java
===================================================================
--- src/main/org/h2/util/BitField.java (revision 1275)
+++ src/main/org/h2/util/BitField.java (working copy)
@@ -15,6 +15,13 @@
private static final int BITS = 64;
private static final int ADDRESS_MASK = BITS - 1;
private long[] data = new long[10];
+
+ /**
+ * Used to cache the value for the {...@link #getLastSetBit} method.
+ */
+ private int lastSetBitIndex = UNSET;
+ private static final int UNSET = -1;
+ private static final int DIRTY = -2;
/**
* Get the index of the last bit that is set.
@@ -22,14 +29,18 @@
* @return the index of the last enabled bit, or -1
*/
public int getLastSetBit() {
- int i = (data.length << ADDRESS_BITS) - 1;
- while (i >= 0) {
- if (get(i)) {
- return i;
- }
- i--;
- }
- return -1;
+ if (lastSetBitIndex == DIRTY) {
+ int i = (data.length << ADDRESS_BITS) - 1;
+ while (i >= 0) {
+ if (get(i)) {
+ lastSetBitIndex = i;
+ }
+ i--;
+ }
+ lastSetBitIndex = UNSET;
+ }
+
+ return lastSetBitIndex;
}
/**
@@ -53,7 +64,7 @@
}
}
}
- return -1;
+ return UNSET;
}
/**
@@ -130,6 +141,11 @@
* @param x the next 8 bits (0 - 255)
*/
public void setByte(int i, int x) {
+ // Mark the last set bit cache dirty only if we absolutely must
+ if (lastSetBitIndex < i+8) {
+ lastSetBitIndex = DIRTY;
+ }
+
int addr = getAddress(i);
checkCapacity(addr);
data[addr] |= ((long) x) << (i & (7 << 3));
@@ -141,6 +157,10 @@
* @param i the index
*/
public void set(int i) {
+ // Update the last set bit cache only if we absolutely must
+ if (lastSetBitIndex < i) {
+ lastSetBitIndex = i;
+ }
int addr = getAddress(i);
checkCapacity(addr);
data[addr] |= getBitMask(i);
@@ -152,6 +172,11 @@
* @param i the index
*/
public void clear(int i) {
+ // If the last set bit is flipped we need to recalculate the index
+ if (i == lastSetBitIndex) {
+ lastSetBitIndex = DIRTY;
+ }
+
int addr = getAddress(i);
if (addr >= data.length) {
return;
