Changeset 7538766


Ignore:
Timestamp:
Jan 19, 2011 2:42:14 PM (9 years ago)
Author:
zzz <zzz@…>
Branches:
master
Children:
7b9f987
Parents:
7a7889b
Message:

DBF/DHS cleanups and speedups

Location:
core/java/src/net/i2p/util
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • core/java/src/net/i2p/util/DecayingBloomFilter.java

    r7a7889b r7538766  
    2121 */
    2222public class DecayingBloomFilter {
    23     private I2PAppContext _context;
    24     private Log _log;
     23    protected final I2PAppContext _context;
     24    protected final Log _log;
    2525    private BloomSHA1 _current;
    2626    private BloomSHA1 _previous;
    27     private int _durationMs;
    28     private int _entryBytes;
     27    protected final int _durationMs;
     28    protected final int _entryBytes;
    2929    private byte _extenders[][];
    3030    private byte _extended[];
     
    3232    private long _longToEntryMask;
    3333    protected long _currentDuplicates;
    34     private boolean _keepDecaying;
    35     private DecayEvent _decayEvent;
     34    protected volatile boolean _keepDecaying;
     35    protected SimpleTimer.TimedEvent _decayEvent;
    3636    /** just for logging */
    37     private String _name;
     37    protected final String _name;
    3838   
    3939    private static final int DEFAULT_M = 23;
     
    4141    private static final boolean ALWAYS_MISS = false;
    4242   
    43     /** noop for DHS */
    44     public DecayingBloomFilter() {}
     43    /** only for extension by DHS */
     44    protected DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context) {
     45        _context = context;
     46        _log = context.logManager().getLog(getClass());
     47        _entryBytes = entryBytes;
     48        _name = name;
     49        _durationMs = durationMs;
     50    }
    4551
    4652    /**
     
    8894            _longToEntryMask = (1l << (_entryBytes * 8l)) -1;
    8995        }
    90         _currentDuplicates = 0;
    9196        _decayEvent = new DecayEvent();
    9297        _keepDecaying = true;
     
    106111   
    107112    public long getCurrentDuplicateCount() { return _currentDuplicates; }
     113
    108114    public int getInsertedCount() {
    109115        synchronized (this) {
     
    111117        }
    112118    }
     119
    113120    public double getFalsePositiveRate() {
    114121        synchronized (this) {
     
    118125   
    119126    /**
    120      * return true if the entry added is a duplicate
    121      *
     127     * @return true if the entry added is a duplicate
    122128     */
    123129    public boolean add(byte entry[]) {
    124130        return add(entry, 0, entry.length);
    125131    }
     132
     133    /**
     134     * @return true if the entry added is a duplicate
     135     */
    126136    public boolean add(byte entry[], int off, int len) {
    127137        if (ALWAYS_MISS) return false;
     
    132142                                               + _entryBytes + "]");
    133143        synchronized (this) {
    134             return locked_add(entry, off, len);
     144            return locked_add(entry, off, len, true);
    135145        }
    136146    }
    137147   
    138148    /**
    139      * return true if the entry added is a duplicate.  the number of low order
     149     * @return true if the entry added is a duplicate.  the number of low order
    140150     * bits used is determined by the entryBytes parameter used on creation of the
    141151     * filter.
     
    144154    public boolean add(long entry) {
    145155        if (ALWAYS_MISS) return false;
    146         synchronized (this) {
    147             if (_entryBytes <= 7)
    148                 entry = ((entry ^ _longToEntryMask) & ((1 << 31)-1)) | (entry ^ _longToEntryMask);
    149                 //entry &= _longToEntryMask;
    150             if (entry < 0) {
    151                 DataHelper.toLong(_longToEntry, 0, _entryBytes, 0-entry);
    152                 _longToEntry[0] |= (1 << 7);
    153             } else {
    154                 DataHelper.toLong(_longToEntry, 0, _entryBytes, entry);
    155             }
    156             return locked_add(_longToEntry, 0, _longToEntry.length);
     156        if (_entryBytes <= 7)
     157            entry = ((entry ^ _longToEntryMask) & ((1 << 31)-1)) | (entry ^ _longToEntryMask);
     158            //entry &= _longToEntryMask;
     159        if (entry < 0) {
     160            DataHelper.toLong(_longToEntry, 0, _entryBytes, 0-entry);
     161            _longToEntry[0] |= (1 << 7);
     162        } else {
     163            DataHelper.toLong(_longToEntry, 0, _entryBytes, entry);
     164        }
     165        synchronized (this) {
     166            return locked_add(_longToEntry, 0, _longToEntry.length, true);
    157167        }
    158168    }
    159169   
    160170    /**
    161      * return true if the entry is already known.  this does NOT add the
     171     * @return true if the entry is already known.  this does NOT add the
    162172     * entry however.
    163173     *
     
    165175    public boolean isKnown(long entry) {
    166176        if (ALWAYS_MISS) return false;
    167         synchronized (this) {
    168             if (_entryBytes <= 7)
    169                 entry = ((entry ^ _longToEntryMask) & ((1 << 31)-1)) | (entry ^ _longToEntryMask);
    170             if (entry < 0) {
    171                 DataHelper.toLong(_longToEntry, 0, _entryBytes, 0-entry);
    172                 _longToEntry[0] |= (1 << 7);
    173             } else {
    174                 DataHelper.toLong(_longToEntry, 0, _entryBytes, entry);
    175             }
     177        if (_entryBytes <= 7)
     178            entry = ((entry ^ _longToEntryMask) & ((1 << 31)-1)) | (entry ^ _longToEntryMask);
     179        if (entry < 0) {
     180            DataHelper.toLong(_longToEntry, 0, _entryBytes, 0-entry);
     181            _longToEntry[0] |= (1 << 7);
     182        } else {
     183            DataHelper.toLong(_longToEntry, 0, _entryBytes, entry);
     184        }
     185        synchronized (this) {
    176186            return locked_add(_longToEntry, 0, _longToEntry.length, false);
    177187        }
    178188    }
    179189   
    180     private boolean locked_add(byte entry[], int offset, int len) {
    181         return locked_add(entry, offset, len, true);
    182     }
    183190    private boolean locked_add(byte entry[], int offset, int len, boolean addIfNew) {
    184191        if (_extended != null) {
     
    196203                if (addIfNew) {
    197204                    _current.locked_insert(_extended);
    198                     _previous.locked_insert(_extended);
    199205                }
    200206                return false;
     
    209215                if (addIfNew) {
    210216                    _current.locked_insert(entry, offset, len);
    211                     _previous.locked_insert(entry, offset, len);
    212217                }
    213218                return false;
  • core/java/src/net/i2p/util/DecayingHashSet.java

    r7a7889b r7538766  
    1818 *      ./router/java/src/net/i2p/router/tunnel/BuildMessageProcessor.java:
    1919 *           32 bytes, peak 10 entries in 1m
     20 *           (320 peak entries seen on fast router)
    2021 *
    2122 *      ./router/java/src/net/i2p/router/transport/udp/InboundMessageFragments.java:
    2223 *           4 bytes, peak 150 entries in 10s
     24 *           (1600 peak entries seen on fast router)
    2325 *
    2426 *      ./router/java/src/net/i2p/router/MessageValidator.java:
    2527 *           8 bytes, peak 1K entries in 2m
     28 *           (36K peak entries seen on fast router)
    2629 *
    2730 *      ./router/java/src/net/i2p/router/tunnel/BloomFilterIVValidator.java:
     
    5861 */
    5962public class DecayingHashSet extends DecayingBloomFilter {
    60     private final I2PAppContext _context;
    61     private final Log _log;
    6263    private ConcurrentHashSet<ArrayWrapper> _current;
    6364    private ConcurrentHashSet<ArrayWrapper> _previous;
    64     private int _durationMs;
    65     private int _entryBytes;
    66     private volatile boolean _keepDecaying;
    67     private final DecayEvent _decayEvent;
    68     /** just for logging */
    69     private final String _name;
    7065    /** synchronize against this lock when switching double buffers */
    7166    private final ReentrantReadWriteLock _reorganizeLock = new ReentrantReadWriteLock(true);
    72    
    7367   
    7468    /**
     
    8478    /** @param name just for logging / debugging / stats */
    8579    public DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes, String name) {
     80        super(durationMs, entryBytes, name, context);
    8681        if (entryBytes <= 0 || entryBytes > 32)
    8782            throw new IllegalArgumentException("Bad size");
    88         _context = context;
    89         _log = context.logManager().getLog(DecayingHashSet.class);
    90         _entryBytes = entryBytes;
    91         _name = name;
    9283        _current = new ConcurrentHashSet(128);
    9384        _previous = new ConcurrentHashSet(128);
    94         _durationMs = durationMs;
    95         _currentDuplicates = 0;
    9685        _decayEvent = new DecayEvent();
    9786        _keepDecaying = true;
     
    112101        return _current.size() + _previous.size();
    113102    }
     103
    114104    /** pointless, only used for logging elsewhere */
    115105    @Override
     
    122112    /**
    123113     * @return true if the entry added is a duplicate
    124      *
    125114     */
    126115    @Override
     
    131120            throw new IllegalArgumentException("Bad entry [" + len + ", expected "
    132121                                               + _entryBytes + "]");
     122        ArrayWrapper w = new ArrayWrapper(entry, off, len);
    133123        getReadLock();
    134124        try {
    135             return locked_add(entry, off, len, true);
     125            return locked_add(w, true);
    136126        } finally { releaseReadLock(); }
    137127    }
     
    159149
    160150    private boolean add(long entry, boolean addIfNew) {
    161         int len = Math.min(8, _entryBytes);
    162         byte[] b = toLong(len, entry);
     151        ArrayWrapper w = new ArrayWrapper(entry);
    163152        getReadLock();
    164153        try {
    165             return locked_add(b, 0, len, addIfNew);
     154            return locked_add(w, addIfNew);
    166155        } finally { releaseReadLock(); }
    167156    }
    168157   
    169     /** from DataHelper, except negative values ok */
    170     private static byte[] toLong(int numBytes, long value) {
    171         byte target[] = new byte[numBytes];
    172         for (int i = 0; i < numBytes; i++)
    173             target[numBytes-i-1] = (byte)(value >>> (i*8));
    174         return target;
    175     }
    176    
    177     /** so many questions... */
    178     private boolean locked_add(byte entry[], int offset, int len, boolean addIfNew) {
    179         ArrayWrapper w = new ArrayWrapper(entry, offset, len);
    180         boolean seen = _current.contains(w);
    181         seen = seen || _previous.contains(w);
     158    /**
     159     *  @param addIfNew if true, add the element to current if it is not already there;
     160     *                  if false, only check
     161     *  @return if the element is in either the current or previous set
     162     */
     163    private boolean locked_add(ArrayWrapper w, boolean addIfNew) {
     164        boolean seen;
     165        // only access _current once. This adds to _current even if seen in _previous.
     166        if (addIfNew)
     167            seen = !_current.add(w);
     168        else
     169            seen = _current.contains(w);
     170        if (!seen)
     171            seen = _previous.contains(w);
    182172        if (seen) {
    183             // why increment if addIfNew == false?
    184             // why not add to current if only in previous?
     173            // why increment if addIfNew == false? Only used for stats...
    185174            _currentDuplicates++;
    186         } else if (addIfNew) {
    187             _current.add(w);
    188             // why add to previous?
    189             _previous.add(w);
    190175        }
    191176        return seen;
     
    271256     */
    272257    private static class ArrayWrapper {
    273         private long _longhashcode;
     258        private final long _longhashcode;
     259
    274260        public ArrayWrapper(byte[] b, int offset, int len) {
    275261            int idx = offset;
    276262            int shift = Math.min(8, 64 / len);
     263            long lhc = 0;
    277264            for (int i = 0; i < len; i++) {
    278265                // xor better than + in tests
    279                 _longhashcode ^= (((long) b[idx++]) << (i * shift));
     266                lhc ^= (((long) b[idx++]) << (i * shift));
    280267            }
     268            _longhashcode = lhc;
     269        }
     270
     271        /** faster version for when storing <= 8 bytes */
     272        public ArrayWrapper(long b) {
     273            _longhashcode = b;
    281274        }
    282275
Note: See TracChangeset for help on using the changeset viewer.