A complex key for guavas Cache (shifting)

Question

I have a point object:

  class Point {
    final int x,y;
    ...
  }

Because these points will be used/created all over the place in my code, I want to start using guavas cache. Unfortuinally the CacheLoader only accept one parameter. Another question here on stackoverflow use a pair object for a similar problem. But I don't like the idea to create a dummy object for every cache request. So I come up with my own workaround:

Because the object is specified by the x and y, I think I can merge(shift) both values into a long, which will be my key.

void test(int x, int y) {
    Long key = (long) ((long) (x) << Integer.SIZE | y);
    Point point = cache.get(key);
}

CacheLoader<Long, Point> loader = new CacheLoader<Long, Point>() {
    public Point load(Long key) throws Exception {
    final int x,y;
        // shift magic
        x = (int) (key >> Integer.SIZE);
        y = key.intValue();
        return new Point(x, y);
    }
};

I'm actually a shift noob. Will this work? Did I miss something? Is this "faster" than the pair class? That's my question!

Yes, I test the code and it works so far I can tell.

yikes. *Please* create a real object (with two well named fields) for the point! You are already creating a 'dummy' object, a java.lang.Long, just more obfuscated. — Dimitris Andreou, Nov 23 '11 at 19:53

bjmi · Accepted Answer · 2011-11-23T13:52:13.623

9

How about this? Your Point class must correctly implement equals() and hashcode().

static class Points {
  static final Interner<Point> INTERNER = Interners.newStrongInterner();

  public static Point cached(final int x, final int y) {
    return INTERNER.intern(new Point(x, y));
  }
}

Your actual purpose was to cache equal objects, right? Than this will suffice your needs. Usage:

Point center = Points.cached(0, 0);

Or an adjusted version of your cache example:

CacheLoader<Point, Point> loader = new CacheLoader<Point, Point>() {
  @Override
  public Point load(final Point point) {
    return point;
  }
}
...
Point center = cache.get(new Point(0, 0));

edited Nov 23 '11 at 13:52

answered Nov 23 '11 at 13:16

bjmi

497
3
12

Hum this Interner is new for me. Looks interesting. Thanks! Of course are `equals` and `hashcode` correctly implement. I don't want that Mr. Bloch put me into the Java-hell :-D – Marcel Jaeschke Nov 23 '11 at 14:13
5

Ouch. Very bad idea. First, you are turning objects with a tiny lifecycle (piece of cake for all garbage collectors) into tenured objects, making all future full gc's slower. Then, this thing grows unbounded, not much different from a memory leak. Third, just to break even in terms of memory, *all cached points would have to be retained at least in two places*. Only if they are reused more would be any memory save. Let alone that these objects are *not* needed to be kept around, other than for the lookup, let alone kept around in two places. I would consider deleting this answer :-\ – Dimitris Andreou Nov 23 '11 at 20:04
You are right. StrongInterner implementation would store points until the end. Interners.newWeakInterner() would do the trick. The benefit is reached only if points are really reused. – bjmi Nov 24 '11 at 08:31
1

WeakInterner wouldn't have any effect, actually, since it's comparing keys using == instead of .equals(). (This is not as well documented as it should be, but the source is pretty clear.) The best solution is almost certainly to just not do any interning at all. Java's GC is great at collecting short-lived, small objects; the overhead is basically negligible. Go ahead and create a fresh Point each time. – Louis Wasserman Nov 28 '11 at 18:42
1

@Louis Wasserman: I disagree w.r.t. the `WeakInterner`. If it used `==`, then it could not intern anything at all. Moreover, in code I can see `.keyEquivalence(Equivalence.equals())`. – maaartinus Sep 24 '12 at 21:52

score 3 · Answer 2 · edited Sep 14 '16 at 09:32

3

It's probably faster (if the difference is measurable at all), but the pair class will make your code much better to understand or reuse. I'd go with a generic Pair class:

public final class Pair<L, R> {

    private final L left;
    private final R right;

    private Pair(L left, R right) {
        this.left = left;
        this.right = right;
    }

    public static <L,R>Pair<L,R> of(L left, R right){
        return new Pair<L, R>(left,right);
    }

    @Override
    public boolean equals(final Object obj) {
        if (obj instanceof Pair) {
            final Pair<?,?> other = (Pair<?,?>) obj;
            return Objects.equal(left,  other.left)
                && Objects.equal(right, other.right);
        } else {
            return false;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(left, right);
    }

    @Override
    public String toString() {
        return MoreObjects.toStringHelper(this)
                      .add("left", left)
                      .add("right", right)
                      .toString();
    }

}

Once you have that in your code base, you will find more than one use for it. Bit shifting is not really Java-like (although many others will disagree).

Guava docs

edited Sep 14 '16 at 09:32

facundofarias

2,973
28
27

answered Nov 23 '11 at 11:27

Sean Patrick Floyd

292,901
67
465
588

Okay, the difference is maybe not measurable. Got it! But what are the disadvantages which you mentioned?! This was one my questions in the first place. – Marcel Jaeschke Nov 23 '11 at 12:29
1

@MarcelJaeschke using objects makes your code readable, understandable and reusable. bit shifting doesn't. If you ask me, it's premature optimization. – Sean Patrick Floyd Nov 23 '11 at 12:34
Yes I know the concept of OOP very well! But I think your way is just a kind of over-engineering! The object point only consist of two int fields. Your pair class has these field two! In fact you create a copy of the object! So you can actually use the object as the key in the first place! I mean (Sorry for the format): Point point = new Point(x,y); Point pointFromCache = cache.get(point); CacheLoader loader = new CacheLoader() { public Point load(Point key) throws Exception { return key; } }; – Marcel Jaeschke Nov 23 '11 at 14:06
@MarcelJaeschke a) don't be afraid of object creation. A current Java VM on a current machine can and does handle thousands of object creations per second. BTW, you are also creating an object with bit shifting because you use a Long object. b) the pair class, as I wrote, makes sense if you reuse it. True, it's overengineered for a single use, but once you have it you'll find many more uses for it. – Sean Patrick Floyd Nov 23 '11 at 14:14
'Point point = new Point(x,y); Point pointFromCache = cache.get(point); CacheLoader loader = new CacheLoader() { public Point load(Point key) throws Exception { return key; } }' – Marcel Jaeschke Nov 23 '11 at 14:14
And talking about over-engineering: a point class seems to me like something that doesn't need to be cached in the first place, caching it probably makes the application (minimally) slower than recreating the Objects, unless you have some complex initialization routines that you are not showing us. – Sean Patrick Floyd Nov 23 '11 at 14:17
Kind of. Several part of the code will always use/create points independently. E.g. >10000000 instances of points (50k are unique). So I think it make sense to cache these points. – Marcel Jaeschke Nov 23 '11 at 14:33

A complex key for guavas Cache (shifting)

2 Answers2