6 ms·
String Deduplication – A new feature in Java 8 Update 20
- dj-wonk 12y agoFrom http://openjdk.java.net/jeps/192 http://openjdk.java.net/jeps/192 > Taking the above into account, the actual expected benefit ends up at around 10% heap reduction. Note that this number is a calculated average based on a wide range of applications. The heap reduction for a specific application could vary significantly both up and down.
- tetha 12y agoI don't think an average is useful in any way here. It will reduce the heap use by some amount, since you reduce the number of char arrays in N strings to some number less than - or equal - than N. There won't be any new arrays allocated. But in my team alone, we have services which deal with many equal but transient strings, some services with long-living, mostly equal strings, some services with long-living, radically different strings. In some of them, I expect rather massive reductions, in others, interning probably has most of the work done already and in others, there's no application or the GC will handle the issue already.
- asdfaoeu 12y agoThe garbage collector needs to store its internal arrays.
- karthikkolli 12y agoWe once maintained a hashmap with key and value as the instance of string to avoid duplication in a search application. Wouldn't that be more beneficial than keeping it in GC if the application uses more strings? Edit: changed avoid deduplication to avoid duplication
- chrisseaton 12y agoWhy did you want to avoid deduplication? You can't even tell it's happened as it only works on the char[] which is internal to the string. Did you find it didn't work as expected.
- karthikkolli 12y agoIt was in a typeahead search application built on 20GB of names. These names have common first names and last names which were stored as different strings. With deduplication, string memory was reduced to 20% Will benchmark that application with +UseStringDeduplication
- chrisseaton 12y agoSo what was the downside of deduplication? Why did you want to avoid it?
- karthikkolli 12y agoSorry deduplication was a typo. Corrected
- chrisseaton 12y agoAh right. The reason they're doing it in the GC rather than in the mutator threads is that it only has an impact on strings long lived enough to be evacuated. Short lived strings don't get deduplicated, and probably don't need to be. Without the GC I don't know how you'd automatically determine that it was a good idea to deduplicate.
- MaxBarraclough 12y ago> We once maintained a hashmap with key and value as the instance of string No love for hashset?
- hibikir 12y agoThis sounds extremely valuable, if just because it requires far less tuning than interning strings. Not so long ago I had to do maintenance on a pretty large Swing application, still stuck on Java 6, that was built around displaying huge amounts of data, holding it all in memory, after retrieving it from some rather slow web services. The poor thing easily ended up using about a couple of gigs, mostly due to the many Strings it held, many of them pretty repetitive. While I tried to reduce the memory footprint, I couldn't just intern everything coming from the service: In Java 6, interned strings come from PermGen. Using a hashmap to allocate everything would have been better than nothing, but the dataset had a whole lot of strings that didn't repeat themselves, so the hashmap would have been far bigger than we needed for the application. What I ended up having to do what to figure out where the data was the most repetitive, and then intern only those strings. I cut memory use by over 30%, but it took days of profiling, evaluating the data and making simple code changes to get there, as opposed to just a runtime flag. Now, I wonder how much better, or worse, it performs that the hashmap solution in cases like the one I faced: a few hundred strings repeated tens of thousands of times, and hundreds of thousands of strings with almost no repetition.
- blinkingled 12y agoWow,that sounds very familiar including the swing app part! Except in my case data came from database and code used StringBuffers leading to massive amounts of duplication. I had to build a COW wrapper and profile the app to find that 95% of the data was only ever read in normal use cases! Thankfully Java tooling is fairly mature - things like MAT and OQL were of great use in finding the memory hogs and leaks.
- cr4zy 12y agoDoes this mean "" == ""?
- jontro 12y agoNo, string deduplication takes place in the internal String char array. Each String will still have it's own object.
- zackangelo 12y agoNot according to the article: > In fact the String Deduplication is almost like interning with the exception that interning reuses the whole String instance, not just the char array.
- chrisseaton 12y agoI think that might mean the opposite of what you think it does. Interning reuses whole String instances. Deduplication is like interning with the exception that it does not reuse the whole String instance, it just reuses the char array. Therefore surely deduplication does not reuse String instances.
- deleted 12y ago[deleted]
- aardvark179 12y agoNo, but that should be true anyway as they are string literals and automatically interned.
- mbq 12y agoAs a curiosity, global string cache is an old feature of R -- however strings are matched upon creation rather than detected by the GC.
- chrisseaton 12y agoThe problem with that is every time you create a string you have to do the work to look it up in the cache. The benefit of the JVM's approach here is that it only bothers to deduplicate it if it is long-lived enough to be evacuated.
- mbq 12y agoSure; in R strings are copied way more frequently than created, so it pays off.
- ris 12y agoIt's also possible to do this in python with the intern () builtin.
- TheLoneWolfling 12y agoRelated: I'm still frustrated by Java randomly (in a minor release, none the less!) switching to copy-on-substring. If I, a random nobody, had something that had its running time increased by a factor of ~50 (simple recursive-descent-ish parser for coercing tabulated data from one format to another - just call substring to trim off the first token repeatedly), how many dev hours were required overall to fix the results of the change? And there's no simple alternative either or way to preserve the old behavior - the simplest one, rolling your own String class or wrapper, ends up being relatively slow and annoying. And "all" of this would be solved by having a proper way of doing array slicing - for things like substring's previous worst case (something like a single character being referenced in a substring holding up a gigabyte+-sized string) Java's garbage collector could recognize that the array was only referenced through slices of part of the array, copy that section into another array (updating references to it), and free the large one. Also, Java's lack of a way to specify that a class is immutable (and that all children classes thereof must also be) is frustrating. Because optimizations like this can and should apply to more than just strings!
- chvid 12y agoAgreed. I am not sure how big a change this is but it seems to me that after Oracle took over Java they have been getting into the bad habit of putting fairly big changes in an "update" only ticking up the minor version after the silly underscore (eg. update 20 is version 1.8.0_20-b26). For example the changes in applet security policies killed thousands of perfectly legit applications that had been running for years - all in an automated rolled out update.
- TheLoneWolfling 12y agoI've largely started avoiding Java applets altogether. Why? Because it's become really really annoying to try to get them to run at all.
- pjmlp 12y agoThose changes are only specific to Oracle's implementation, there are lots of others to choose from. Most of those changes don't have any relation whatsoever with the Java Language Specification or Java Virtual Machine Specification.
- nly 12y agoBoost flyweight is pretty useful for doing this in C++ http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/index.html http://www.boost.org/doc/libs/1_56_0/libs/flyweight/doc/inde...
- phunge 12y agoHere's a counterargument for this, just to be a fuddy-duddy: One of the key activities in programming is reasoning about time and space cost, and this is a space optimization that's nondeterministic. It kicks in sometimes, or sometimes not at all, and happens behind the scenes at garbage collection time when it's nearly invisible. If you're sloppy, your program may have a huge asymptotic space usage, and this may paper over it. But the impl has heuristics, it may not work all the time -- even their example program needed Thread.sleep() calls! Unpredictable semantics help nobody. So I always liked explicit string interning (whatup, Lisp!). All the same, faster is better and I'm sure this makes things faster. Oh and can we talk about how broken it was that Java 6 and under had a fixed size pool for .intern()'d strings?
- peterashford 12y agoIt's controlled with a switch. Don't turn it on.
- brandonbloom 12y agoYour applications already sit upon a mountain of non-determinism. A typical web app runs against a database with a genetic query optimizer, on top of a VM with a concurrent generational GC, sharing virtual memory with a dozen other processes, arranged in a massive pyramid of caches, which are competing for CPU time from a multi-core monstrosity of a data-flow engine. The sooner we as programmers embrace stochastic methods, the better.
- gioele 12y agoFor those interested in the same feature in plain old C, have a look at the DSO Howto, section 2.4.2 "Forever const" and the LD flags SHF_MERGE and SHF_STRING. With a little bit of magic, C compilers and linkers are even allowed to turn (simplified example) const char s1[] = "some string"; const char s2[] = "string"; into const char s1[] = "some string"; const char s2[] = s1+5; and place these constants in a read-only section shared between multiple loaded instances of the same library or program.
- riffraff 12y agoI think it's standard java behaviour to .intern string constants appearing in code (i.e. since they are immutable, just share them). The new thing is that the JVM is going to do this automatically for strings that _don't_ exist at compile time, IIUC.
- pjmlp 12y agoThis is only specific to the Oracle JVM.