lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Patrick Eger (JIRA)" <j...@apache.org>
Subject [jira] Commented: (LUCENE-1607) String.intern() faster alternative
Date Wed, 29 Apr 2009 18:41:30 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-1607?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12704246#action_12704246
] 

Patrick Eger commented on LUCENE-1607:
--------------------------------------

As a quick comment on the implementation, i notice that it is possible (with reasonable probability)
for hash collisions to result in re-interning a pair of strings multiple times. For example,
a codepath that traverses across 32 unique string datapoints (say, in an inner loop somewhere),
would have a minimum 3% probability of colliding and re-interning 2 strings every time through
the loop. Because of the birthday paradox, it becomes likely to have such a situation (50%
probability with ~150 unique values).

These are the probabilities of collision, assuming random distribution and perfect hashing.
In real life the distribution will not be so random (string.hashCode() & MASK) so these
will be "best case".
2 datapoints: collision prob = 0.006104%
4 datapoints: collision prob = 0.036617%
8 datapoints: collision prob = 0.170779%
16 datapoints: collision prob = 0.729976%
32 datapoints: collision prob = 2.983863%
64 datapoints: collision prob = 11.591861%
128 datapoints: collision prob = 39.188158%
256 datapoints: collision prob = 86.501947%


Practically this may or may not matter. My thought is that some sort of fast LRU structure
would be better, but of course creating something like this without locking may be tricky.
Another idea might be to support some form of limited hash-chaining or probing in the table,
which would mitigate the damage of a collision significantly.


for reference, python code for calculating birthday/hash collisions, shamelessly stolen:
--------------------
def bp(n, d):
	v = 1.0
	for i in range(n):
		v = v * (1 - float(i)/d)
	return 1 - v

for n in [2, 4, 8, 16, 32, 64, 128, 256]:
	print "%i datapoints: collision prob = %f%%" % (n, bp(n, 16*1024)*100)

> String.intern() faster alternative
> ----------------------------------
>
>                 Key: LUCENE-1607
>                 URL: https://issues.apache.org/jira/browse/LUCENE-1607
>             Project: Lucene - Java
>          Issue Type: Improvement
>            Reporter: Earwin Burrfoot
>             Fix For: 2.9
>
>         Attachments: intern.patch, LUCENE-1607.patch, LUCENE-1607.patch, LUCENE-1607.patch,
LUCENE-1607.patch
>
>
> By using our own interned string pool on top of default, String.intern() can be greatly
optimized.
> On my setup (java 6) this alternative runs ~15.8x faster for already interned strings,
and ~2.2x faster for 'new String(interned)'
> For java 5 and 4 speedup is lower, but still considerable.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Mime
View raw message