1

I'm trying to collect data about execution time and compare the times when enqueuing and dequeuing a heap tree vs bst. For the time elapsed I use nanoTime().

Everything looks fine with the time elapsed when enqueuing/dequeuing heap trees, both unsorted and sorted. Also when enqueuing bst. When I'm trying to dequeue a sorted bst with say 700000 elements the execution takes very long. That's okey, it's similar when enqueuing a sorted bst.

The problem is that the time elapsed for execution is not correct. The time should be something about 15000 milliseconds, but I get an answer about 0,5 milliseconds (or 459053 ns).

First I'm enqueuing a bst with 640000 elements (integers), then sorting the tree. What I'm interesting in is the execution time when enqueuing this bst (with already 640000 sorted elements).

Here is my code (part of it):

public static void main(String[] args)
            throws DuplicateItemException, FileNotFoundException, IOException, EmptyQueueException {

        final String pathFullList = "Files/data_640000.txt";
        final String pathPartialList = "Files/data_6400.txt";
        final int SIZE_SEVEN = 640000;
        final int SIZE_FOR_LIST_TWO = 6400;

        BSTPriorityQueue<Integer> bstQueue = new BSTPriorityQueue<Integer>();
        bstQueue.clear();

        List<Integer> listOne = new ArrayList<Integer>();
        listOne = loadList(pathFullList, SIZE_SEVEN);

        Collections.sort(listOne);
        long execTimeForSort = System.nanoTime() - t2;
        System.out.println("Time for sort: " + execTimeForSort);

        enqueueBstTree(listOne, bstQueue);
        System.out.println("Size of hptree before enqueue: " + hPQueue.size() + 
                "\n" + "Size of bsttree before enqueue: " + bstQueue.size());

        List<Integer> listTwo = new ArrayList<Integer>();
        listTwo = loadList(pathPartialList, SIZE_FOR_LIST_TWO);

        long t1 = System.nanoTime();
        dequeueBstTree(listTwo, bstQueue, SIZE_FOR_LIST_TWO);
        long execTime = System.nanoTime() - t1;

        System.out.println("Time difference for enqueue/dequeue: " + execTime);
        System.out.println("Size of hptree after enqueue/dequeue: " + hPQueue.size() + 
                "\n" + "Size of bsttree after enqueue/dequeue: " + bstQueue.size());
    }

This code takes maybe 20 minutes to execute. The answer I get from execTime is 459053 nanoseconds.

ami
  • 27
  • 2
  • Have you tried using `System.currentTimeMillis()` instead? That method is more accurate, though less precise – lucasvw Nov 20 '19 at 17:16
  • 1
    @lucasvw `currentTimeMillis()` is definitely not more accurate, it's cheaper to call but in most cases has lower granularity and is subject to drift between cores (depends on the OS function used). – Karol Dowbecki Nov 20 '19 at 17:20
  • How did you come up with the 15s time that it "should" be? If that's how long the program takes to run then it's possible that it's another step taking that time and the dequeue duration is accurate. – Thomas Nov 20 '19 at 17:22
  • "What I'm interesting in is the execution time when enqueuing this bst " Your program does not appear to contain code to time the `enqueueBstTree` method. – that other guy Nov 20 '19 at 17:26
  • The "should" be time is about 15 minutes and is about dequeuing a sorted binary search tree. I guess you got a worst case scenario with this combo. I'm consequent when invoking the dequeueBstTree method in counting the time elapsed for every case. – ami Nov 20 '19 at 22:02
  • Use [JMH](https://openjdk.java.net/projects/code-tools/jmh/) for your benchmarks. – erickson Nov 20 '19 at 22:14

1 Answers1

5

Your System.nanoTime() usage is correct however execTime is measured just for dequeueBstTree() method call. If the entire program execution takes 20 minutes then the majority of the time is spent outside of the measured dequeueBstTree() method call. It could be anything: JVM startup, heap resizing, GC cycle, other logic in the main()...

What you most likely want to do is to write a correct micro-benchmark just for dequeueBstTree().

Karol Dowbecki
  • 43,645
  • 9
  • 78
  • 111
  • Thank you for your answer. I will try to write a correct microbenhmark for dequeueBstTree. However, I did test execTime even for other subjects in my code, like the sorting. For example, I did a test for evaluated time for sorting, which was shown immediately and with bigger evaluated time than the one for dequeueBstTree that last for about 20 min. But, like I said, I will try your proposed solution. Thank you again. – ami Nov 20 '19 at 22:03