001: /*
002: (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP, all rights reserved.
003: [See end of file]
004: $Id: TripleCache.java,v 1.6 2008/01/02 12:06:55 andy_seaborne Exp $
005: */
006:
007: package com.hp.hpl.jena.graph;
008:
009: /**
010: TripleCache caches triples according to their SPO members, to reduce store
011: turnover at the expense of some added computation. The cache is implemented
012: as an array indexed by the (reduced) hashCode of the triples it stores.
013: Each slot is treated independantly and only the most recent stored triple is
014: remembered - there is no weighting, LRU, or anything like that.
015:
016: @author kers
017: */
018: public class TripleCache {
019: /**
020: The size of the cache array. 1000 gets 80% hits when running the Jena
021: test suite and all the slots get used. 10000 gets about 83% and *almost* all
022: the slots get used. Absent real performance indicators, 1000 will do for
023: now.
024: */
025: public static int SIZE = 1000;
026:
027: /**
028: The array holding the cached triples.
029: */
030: private Triple[] triples = new Triple[SIZE];
031:
032: /**
033: Cache the triple <code>t</code> by storing it in the slot with the its reduced
034: hash. Any triple already in that slot vanishes. Answer that triple.
035: */
036: public Triple put(Triple t) {
037: triples[(t.hashCode() & 0x7fffffff) % SIZE] = t;
038: return t;
039: }
040:
041: private static int count = 0;
042: private int id = ++count;
043: private int hits = 0;
044: private int misses = 0;
045:
046: /**
047: Answer the number of occupied slots in the cache array.
048: */
049: private int count() {
050: int result = 0;
051: for (int i = 0; i < SIZE; i += 1)
052: if (triples[i] != null)
053: result += 1;
054: return result;
055: }
056:
057: /**
058: Answer any triple in the cache with subject <code>s</code>, predicate
059: <code>p</code>, and object <code>o</code>, or <code>null</code> if
060: no such triple exists.
061: <p>
062: The implementation looks in the slot with the same reduced hashCode as
063: the SPO combination would have. If the triple there has the same SPO,
064: it is returned; otherwise <code>null</code> is returned.
065: */
066: public Triple get(Node s, Node p, Node o) {
067: Triple already = triples[(Triple.hashCode(s, p, o) & 0x7fffffff)
068: % SIZE];
069: if (false) {
070: if (already == null || !already.sameAs(s, p, o))
071: misses += 1;
072: else
073: hits += 1;
074: if ((hits + misses) % 1000 == 0)
075: System.err.println(">> cache [" + id + "] hits: "
076: + hits + ", misses: " + misses + ", occ: "
077: + count() + "/" + SIZE);
078: }
079: return already == null || !already.sameAs(s, p, o) ? null
080: : already;
081: }
082: }
083: /*
084: (c) Copyright 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
085: All rights reserved.
086:
087: Redistribution and use in source and binary forms, with or without
088: modification, are permitted provided that the following conditions
089: are met:
090:
091: 1. Redistributions of source code must retain the above copyright
092: notice, this list of conditions and the following disclaimer.
093:
094: 2. Redistributions in binary form must reproduce the above copyright
095: notice, this list of conditions and the following disclaimer in the
096: documentation and/or other materials provided with the distribution.
097:
098: 3. The name of the author may not be used to endorse or promote products
099: derived from this software without specific prior written permission.
100:
101: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
102: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
103: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
104: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
105: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
106: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
107: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
108: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
109: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
110: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
111: */
|