src/tests/gov/nasa/jpf/util/PSIntMapTest.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 import gov.nasa.jpf.util.test.TestJPF;
  22 import java.util.Arrays;
  23 import java.util.BitSet;
  24 import java.util.HashMap;
  25 import java.util.Iterator;
  26 import java.util.Map;
  27 import java.util.Random;
  28 import org.junit.Test;
  29
  30 /**
  31  * regression test for PSIntMap
  32  */
  33 public class PSIntMapTest extends TestJPF {
  34
  35   PSIntMap<Integer> createPersistentIntMap(){
  36     return new PSIntMap<Integer>();
  37   }
  38
  39   PSIntMap<Integer> set (PSIntMap<Integer> m, int i){
  40     return m.set(i, Integer.valueOf(i));
  41   }
  42
  43   PSIntMap<Integer> set (PSIntMap<Integer> m, int[] data){
  44     for (int i=0; i<data.length; i++){
  45       int v = data[i];
  46       if (v >= 0){
  47         m = m.set( v, Integer.valueOf(v));
  48       } else {
  49         m = m.remove(-v);
  50       }
  51     }
  52     return m;
  53   }
  54
  55   static class IntegerProcessor implements Processor<Integer>{
  56     int count=0;
  57
  58     @Override
  59         public void process( Integer i){
  60       if (count++ > 0){
  61         System.out.print(',');
  62       }
  63       System.out.print(i);
  64     }
  65
  66     public int getCount(){
  67       return count;
  68     }
  69   }
  70
  71   static void dump (String prefix, PSIntMap<Integer> map, String postfix){
  72     if (prefix != null) {
  73       System.out.print(prefix);
  74       System.out.print(' ');
  75     }
  76
  77     System.out.print(map.getClass().getSimpleName() + " {");
  78     map.process( new IntegerProcessor());
  79     System.out.print('}');
  80
  81     if (postfix != null){
  82       System.out.print(' ');
  83       System.out.print(postfix);
  84     }
  85   }
  86
  87   static void dump (PSIntMap<Integer> map){
  88     dump(null,map, "\n");
  89   }
  90
  91   static void assertNullValue (PSIntMap<Integer> map, int key){
  92     Integer v = map.get(key);
  93     if (v != null){
  94       fail("non-null value for: " + key + " = " + v);
  95     }
  96   }
  97
  98   static void assertNonNullValue (PSIntMap<Integer> map, int key){
  99     Integer v = map.get(key);
 100     if (v == null || v.intValue() != key){
 101       fail("wrong value for: " + key + " = " + v);
 102     }
 103   }
 104
 105   static void assertEquals( PSIntMap<Integer> map, int[] data){
 106     int[] a = data.clone();
 107     Arrays.sort(a);
 108
 109     System.out.print("assertEquals {");
 110     for (int i=0; i<data.length; i++){
 111       if (i > 0){
 112         System.out.print(',');
 113       }
 114       System.out.print(a[i]);
 115     }
 116     System.out.println('}');
 117
 118     assertTrue( map.size() == data.length);
 119
 120     int[] b = new int[data.length];
 121     int j=0;
 122     for (Integer v : map){
 123       int i = v.intValue();
 124       b[j++] = i;
 125     }
 126     Arrays.sort(b);
 127
 128     for (int i=0; i<a.length; i++){
 129       if (a[i] != b[i]){
 130         fail("different values : " + a[i] + ',' + b[i]);
 131       }
 132     }
 133   }
 134
 135   //--- the tests
 136
 137   @Test
 138   public void testSingleAdd(){
 139     PSIntMap<Integer> m = createPersistentIntMap();
 140     assertTrue( m.size() == 0);
 141
 142     m = set( m, 0);
 143     dump("0: ", m, "\n");
 144     assertTrue( m.size() == 1);
 145     assertNonNullValue( m, 0);
 146     assertNullValue( m, 42);
 147
 148     m = new PSIntMap<Integer>();
 149     m = set( m, 42);
 150     dump("42: ", m, "\n");
 151     assertTrue( m.size() == 1);
 152     assertNullValue( m, 0);
 153     assertNonNullValue( m, 42);
 154
 155     int k = 32*32*32*32 + 1;
 156     m = new PSIntMap<Integer>();
 157     m = set( m, k);
 158     dump("32**4 + 1: ", m, "\n");
 159     assertTrue( m.size() == 1);
 160     assertNullValue( m, 0);
 161     assertNonNullValue( m, k);
 162     m.printOn(System.out);
 163   }
 164
 165   @Test
 166   public void testMultiAdd(){
 167     PSIntMap<Integer> m = createPersistentIntMap();
 168
 169     int[] data = { 0,1, 32, 4,10, 666,669, 36, 37 };
 170     m = set( m, data);
 171
 172     dump(m);
 173     //m.printOn(System.out);
 174
 175     assertEquals( m, data);
 176   }
 177
 178   @Test
 179   public void testConsecutiveAdd(){
 180     int len = 32*32*32;
 181     PSIntMap<Integer> m = createPersistentIntMap();
 182     for (int i=0; i<len; i++){
 183       m = set(m, i);
 184     }
 185
 186     for (int i=0; i<len; i++){
 187       Integer v = m.get(i);
 188       assertNonNullValue( m, i);
 189     }
 190
 191     System.out.println("m.size() = " + m.size());
 192     assertTrue(m.size() == len);
 193   }
 194
 195   @Test
 196   public void testConsecutiveAddRemove(){
 197     int len = 32*32*32;
 198     PSIntMap<Integer> m = createPersistentIntMap();
 199     for (int i=0; i<len; i++){
 200       m = set(m, i);
 201     }
 202
 203     for (int i=0; i<len; i++){
 204       Integer v = m.get(i);
 205       assertNonNullValue( m, i);
 206     }
 207
 208     for (int i=len-1; i>= 0; i--){
 209       m = m.remove(i);
 210     }
 211
 212     System.out.println("m.size() = " + m.size());
 213     assertTrue(m.size() == 0);
 214   }
 215
 216   @Test
 217   public void testPredicateRemoval(){
 218     PSIntMap<Integer> m = createPersistentIntMap();
 219
 220     int[] data = { 0,1, 32, 4,10, 666,669, 36, 37, 95,97 };
 221     m = set( m, data);
 222
 223     dump("before removal:", m, "\n");
 224
 225     Predicate<Integer> pred = new Predicate<Integer>(){
 226       @Override
 227         public boolean isTrue(Integer i){
 228         return ((i & 1) != 0);
 229       }
 230     };
 231
 232     m = m.removeAllSatisfying(pred);
 233
 234     dump("after removal:", m, "\n");
 235     m.printOn(System.out);
 236   }
 237
 238   @Test
 239   public void testRangePredicateRemoval(){
 240     PSIntMap<Integer> m = createPersistentIntMap();
 241     int len = 20000;
 242     for (int i=0; i<len; i++){
 243       m = set(m, i);
 244     }
 245
 246     // completely remove first value node
 247     Predicate<Integer> pred = new Predicate<Integer>(){
 248       @Override
 249         public boolean isTrue (Integer n){
 250         return (n <= 31);
 251       }
 252     };
 253     m = m.removeAllSatisfying(pred);
 254
 255     System.out.println("m.size() = " + m.size());
 256     assertTrue( m.size() == (len - 32));
 257     for (int i=0; i<32; i++){
 258       assertTrue( m.get(i) == null);
 259     }
 260     len -= 32;
 261
 262     // remove all but one value from the second node
 263     pred = new Predicate<Integer>(){
 264       @Override
 265         public boolean isTrue (Integer n){
 266         return (n >32 && n <= 63);
 267       }
 268     };
 269     m = m.removeAllSatisfying(pred);
 270     System.out.println("m.size() = " + m.size());
 271     assertTrue( m.size() == (len - 31));
 272     assertTrue( m.get(32) != null);
 273     for (int i=33; i<64; i++){
 274       assertTrue( m.get(i) == null);
 275     }
 276     len -= 31;
 277
 278     // remove all but one from bitmap node
 279     pred = new Predicate<Integer>(){
 280       @Override
 281         public boolean isTrue (Integer n){
 282         return (n == 64);
 283       }
 284     };
 285     m = m.removeAllSatisfying(pred);
 286     pred = new Predicate<Integer>(){
 287       @Override
 288         public boolean isTrue (Integer n){
 289         return (n >= 64 && n < 95);
 290       }
 291     };
 292     m = m.removeAllSatisfying(pred);
 293     for (int i=64; i<95; i++){
 294       assertTrue( m.get(i) == null);
 295     }
 296     assertTrue( m.get(95) != null);
 297   }
 298
 299   @Test
 300   public void testHeapPattern(){
 301     Random r = new Random(42);
 302     final BitSet removed = new BitSet();
 303
 304     Predicate<Integer> pred = new Predicate<Integer>(){
 305       @Override
 306         public boolean isTrue (Integer n){
 307         return removed.get(n.intValue());
 308       }
 309     };
 310
 311     PSIntMap<Integer> m = createPersistentIntMap();
 312     int max = 20000;
 313     for (int i=0; i<max; i++){
 314       m = set(m, i);
 315
 316       if ((i > 0) && (i % 500) == 0){
 317          for (int j=0; j<120; j++){
 318            int k = r.nextInt(i);
 319            removed.set(k);
 320          }
 321
 322          m = m.removeAllSatisfying(pred);
 323       }
 324     }
 325
 326     System.out.println("m.size() = " + m.size());
 327     int nRemoved = removed.cardinality();
 328     assertTrue( m.size() == (max - nRemoved));
 329
 330     int n = 0;
 331     for (int i=0; i<max; i++){
 332       if (removed.get(i)){
 333         assertTrue( m.get(i) == null);
 334       } else {
 335         assertTrue( m.get(i) != null);
 336         n++;
 337       }
 338     }
 339     assertTrue( n == (max - nRemoved));
 340   }
 341
 342
 343   //--- benchmarks
 344
 345   final static int NSTATES = 20000;
 346   final static int NOBJECTS = 2000;
 347   final static int NGC = 400;
 348
 349
 350   public void benchmark (){
 351     long t1, t2;
 352
 353     //--- PersistentIntMap
 354     Predicate<Integer> pred = new Predicate<Integer>() {
 355       @Override
 356         public boolean isTrue (Integer o) {
 357         int i = o.intValue();
 358         return (i < NGC);
 359       }
 360     };
 361
 362     Runtime.getRuntime().gc();
 363     t1 = System.currentTimeMillis();
 364     for (int l=0; l<NSTATES; l++) {
 365       PSIntMap<Integer> t = createPersistentIntMap();
 366
 367       //--- allocations
 368       for (int i=0; i<NOBJECTS; i++){
 369         t = t.set(i,  Integer.valueOf(i));
 370       }
 371
 372       //--- lookup
 373       for (int i=0; i<NOBJECTS; i++) {
 374         Integer o = t.get(i);
 375       }
 376
 377       //--- gc
 378       t = t.removeAllSatisfying(pred);
 379
 380       //--- no store/backtrack costs for container
 381     }
 382     t2 = System.currentTimeMillis();
 383     System.out.println("PersistentIntMap (" + NSTATES + " cycles): " + (t2 - t1));
 384
 385
 386     //--- HashMap
 387     Runtime.getRuntime().gc();
 388     t1 = System.currentTimeMillis();
 389     for (int l=0; l<NSTATES; l++) {
 390       HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
 391       //--- allocations
 392       for (int i=0; i<NOBJECTS; i++){
 393         m.put(i, i);
 394       }
 395
 396       //--- lookup
 397       for (int i=0; i<NOBJECTS; i++) {
 398         Integer o = m.get(i);
 399       }
 400
 401       //--- gc
 402       for (Iterator<Map.Entry<Integer,Integer>> it = m.entrySet().iterator(); it.hasNext();) {
 403         Map.Entry<Integer, Integer> e = it.next();
 404         if (pred.isTrue(e.getValue())) {
 405           it.remove();
 406         }
 407       }
 408
 409       //--- 2 x clone (upon store and backtrack)
 410       m = (HashMap<Integer,Integer>)m.clone();
 411       m = (HashMap<Integer,Integer>)m.clone();
 412     }
 413     t2 = System.currentTimeMillis();
 414     System.out.println("HashMap (" + NSTATES + " cycles): " + (t2 - t1));
 415
 416     //--- ObjVector (needs to be adjusted for holes -> increased size)
 417     Runtime.getRuntime().gc();
 418     t1 = System.currentTimeMillis();
 419     for (int l=0; l<NSTATES; l++) {
 420       ObjVector<Integer> v = new ObjVector<Integer>();
 421       //--- allocations
 422       for (int i=0; i<NOBJECTS; i++){
 423         v.set(i, i);
 424       }
 425
 426       //--- lookup
 427       for (int i=0; i<NOBJECTS; i++) {
 428         Integer o = v.get(i);
 429       }
 430
 431       //--- gc
 432       v.clearAllSatisfying(pred);
 433
 434       //--- snap & restore
 435       ObjVector.Snapshot<Integer> snap = v.getSnapshot();
 436       v.restore(snap);
 437     }
 438     t2 = System.currentTimeMillis();
 439     System.out.println("ObjVector (" + NSTATES + " cycles): " + (t2 - t1));
 440
 441   }
 442
 443 }