1   /*
2    *   Licensed to the Apache Software Foundation (ASF) under one
3    *   or more contributor license agreements.  See the NOTICE file
4    *   distributed with this work for additional information
5    *   regarding copyright ownership.  The ASF licenses this file
6    *   to you under the Apache License, Version 2.0 (the
7    *   "License"); you may not use this file except in compliance
8    *   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,
13   *   software distributed under the License is distributed on an
14   *   "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *   KIND, either express or implied.  See the License for the
16   *   specific language governing permissions and limitations
17   *   under the License.
18   *
19   */
20  package org.apache.directory.server.core.avltree;
21  
22  
23  import java.io.File;
24  import java.io.FileInputStream;
25  import java.io.FileOutputStream;
26  import java.io.ObjectInputStream;
27  import java.io.ObjectOutputStream;
28  import java.util.Comparator;
29  import java.util.HashSet;
30  import java.util.Set;
31  
32  import org.junit.AfterClass;
33  import org.junit.Before;
34  import org.junit.Test;
35  import org.slf4j.Logger;
36  import org.slf4j.LoggerFactory;
37  
38  
39  /**
40   * 
41   * Performance test cases for AVLTree implementation.
42   *
43   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
44   * @version $Rev$, $Date$
45   */
46  public class AvlTreePerfTest
47  {
48      AvlTree<Integer> tree;
49      
50      static String tempDir = System.getProperty( "java.io.tmpdir" );
51     
52      static File setSerialFile = new File( tempDir + File.separator + "hashset.ser" );
53      static File treeSerialFile = new File( tempDir + File.separator + "avltree.ser" );
54      
55      Set<Integer> set;
56      
57      long start, end;
58  
59      int numKeys = 100000;
60  
61      Comparator<Integer> comparator = new Comparator<Integer>() 
62      {
63        public int compare( Integer i1, Integer i2 )
64        {
65            return i1.compareTo( i2 );
66        }
67      
68      };
69      
70      AvlTreeMarshaller<Integer> treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
71  
72      private final static Logger LOG = LoggerFactory.getLogger( AvlTreePerfTest.class );
73      
74      @Before
75      public void createTree()
76      {
77        tree = new AvlTree<Integer>( new Comparator<Integer>() 
78            {
79  
80              public int compare( Integer i1, Integer i2 )
81              {
82                  return i1.compareTo( i2 );
83              }
84            
85            });  
86        
87        set = new HashSet<Integer>();
88        
89        start = end = 0;
90      }
91      
92      
93      @AfterClass
94      public static void deleteFiles()
95      {
96          setSerialFile.delete();
97          treeSerialFile.delete();
98      }
99      
100     
101     @Test
102     public void testRBTreeInsertPerf()
103     {
104         start = System.nanoTime();
105         
106         for( int i=0; i < numKeys; i++ )
107         {
108             set.add( i );
109         }
110         
111         end = System.nanoTime();
112      
113         LOG.info( "total time for inserting " + numKeys + " items into the RBTree-->" +  getTime( start, end ) );
114         
115     }
116 
117     
118     @Test
119     public void testRBTreeLookupPerf()
120     {
121         for( int i=0; i < numKeys; i++ )
122         {
123             set.add( i );
124         }
125         
126        start = System.nanoTime();
127        
128         set.contains( 70 );
129         set.contains( -1000 );
130         set.contains( 10 );
131         set.contains( 90 );
132         set.contains( 9999 );
133         
134        end = System.nanoTime();
135        
136        LOG.info( "total time took to read an item from set " + getTime( start, end ) ) ;
137     }
138     
139     
140     @Test
141     public void testRemoveFromRBTree()
142     {
143         for( int i=0; i < numKeys; i++ )
144         {
145             set.add( i );
146         }
147         
148         start = System.nanoTime();
149         
150         set.remove( 90 );
151         set.remove( 912 );
152         set.remove( -1 );
153         set.remove( 192 );
154         
155         end = System.nanoTime();
156         
157         LOG.info( "total time took to remove an item from set " + getTime( start, end ) ) ;
158 
159     }
160     
161     
162     @Test
163     public void testAvlTreeInsertPerf()
164     {
165         start = System.nanoTime();
166         
167         for( int i=0; i < numKeys; i++ )
168         {
169             tree.insert( i );
170         }
171 
172         end = System.nanoTime();
173         
174         LOG.info("total time for inserting " + numKeys + " items into the AVLTree-->" + getTime(start, end));
175     }
176     
177     
178     @Test
179     public void testAVLTreeLookupPerf()
180     {
181         
182         for( int i=0; i < numKeys; i++ )
183         {
184             tree.insert( i );
185         }
186         
187         start = System.nanoTime();
188         
189         tree.find( 70 );
190         tree.find( -1000 );
191         tree.find( 10 );
192         tree.find( 90 );
193         tree.find( 9999 );
194         
195         end = System.nanoTime();
196         
197         LOG.info("total time took to read an item from tree " + getTime( start, end ) ) ;
198     }
199     
200     
201     @Test
202     public void testAVLTreeRemovePerf()
203     {
204         for( int i=0; i < numKeys; i++ )
205         {
206             tree.insert( i );
207         }
208         
209         start = System.nanoTime();
210         
211         tree.remove( 90 );
212         tree.remove( 912 );
213         tree.remove( -1 );
214         tree.remove( 192 );
215         
216         end = System.nanoTime();
217         
218         LOG.info("total time took to remove an item from AVLTree " + getTime( start, end ) ) ;
219 
220     }
221     
222     
223     @Test
224     public void testRBTreeSerializationPerf() throws Exception
225     {
226         FileOutputStream fout = new FileOutputStream( setSerialFile );
227         ObjectOutputStream objOut = new ObjectOutputStream( fout );
228         
229         Set<Integer> set = new HashSet<Integer>();
230         
231         for( int i=0; i < numKeys; i++ )
232         {
233             set.add( i );
234         }
235         
236         long start = System.nanoTime();
237         
238         objOut.writeObject( set );
239         objOut.flush();
240         objOut.close();
241         
242         long end = System.nanoTime();
243         
244         LOG.info( "total time taken for serializing HashSet ->" + getTime( start, end ) );
245     }
246     
247     
248     @SuppressWarnings("unchecked")
249 	@Test
250     public void testRBTreeDeserializationPerf() throws Exception
251     {
252      // read test
253         FileInputStream fin = new FileInputStream( setSerialFile );
254         ObjectInputStream objIn = new ObjectInputStream( fin );
255         
256         start = System.nanoTime();
257         
258         set = ( HashSet ) objIn.readObject();
259         
260         end = System.nanoTime();
261         
262         LOG.info("total time taken for reconstructing a serialized HashSet ->" + getTime( start, end ) );
263     }
264     
265     
266     @Test
267     public void testAVLTreeSerializationPerf() throws Exception
268     {
269       
270       for( int i=0; i < numKeys; i++ )
271       {
272           tree.insert( i );
273       }
274       
275       FileOutputStream fout = new FileOutputStream( treeSerialFile );
276     
277       start = System.nanoTime();
278       
279       fout.write( treeMarshaller.serialize( tree ) );
280       fout.flush();
281       fout.close();
282       
283       end = System.nanoTime();
284       
285       LOG.info( "total time taken for serializing AVLTree ->" + getTime( start, end ) );
286     }
287 
288     
289     @Test
290     public void testAVLTreeDeserializationPerf() throws Exception
291     {
292         FileInputStream fin = new FileInputStream( treeSerialFile );
293 
294         byte data[] = new byte[ ( int ) treeSerialFile.length() ];
295         
296         start = System.nanoTime();
297         
298         fin.read(data);
299         tree = (AvlTree<Integer>) treeMarshaller.deserialize( data );
300         
301         end = System.nanoTime();
302         LOG.info("total time taken for reconstructing a serialized AVLTree ->" + getTime( start, end ) );
303     }
304     
305     
306     /**
307      * calculates the total time taken in milli seconds by taking the start and end time in nano seconds. 
308      */
309     private String getTime(long nanoStartTime, long nanoEndTime)
310     {
311         long temp = nanoEndTime - nanoStartTime;
312         
313         if( temp == 0)
314         {
315             return "0 msec";
316         }
317         
318        double d = temp / (1000 * 1000);
319         
320        return String.valueOf( d ) + " msec";
321     }
322 }