7 Replies Latest reply: Dec 14, 2010 10:13 AM by 796440 RSS

    Searching most time-optimized java implementation of a stack

    823519
      Hi.

      I tried and failed to find time efficient implementation of a stack in the JDK 1.6. I searched in the java.util package, browsed throw the javadoc to find the most simplest class implementing a stack, but found only high-level classes as Stcak, Deque, LinkedList, wich offers too much functionnalities.
      I've tested the time needed to do for example a pop() or a peek() call and saw that it needs arround 5 µs.
      I'm looking for a simplest class (if it exists), with which pushing and poping needs only several nanoseconds.

      It would be great from anybody to help me to tell me first if such a class exists, and then tell me where to find it.

      Thank's in advanace.
        • 1. Re: Searching most time-optimized java implementation of a stack
          796440
          Either your test is faulty or you have a fairly low-powered machine. My laptop takes about 0.1 μs to offer() and about 0.03 μs to poll(), using LinkedList.
          • 2. Re: Searching most time-optimized java implementation of a stack
            802316
            You need to see how your test behaves after it is warmed up. Try running the test for at least 2 seconds ignoring the first 10,000 samples (while the JVM warms up)

            btw @jverd, you might need to run it for longer, and you might find it even faster. ;)

            The following prints
            Average 27 ns.
            to offer and pop an entry from the list.
            public static void main(String... args) {
                LinkedList<Integer> ll = new LinkedList<Integer>();
                long start = 0;
                int runs = 50 * 1000 * 1000;
                for (int i = -10000; i < runs; i++) {
                    if (i == 0) start = System.nanoTime();
                    ll.offer(1);
                    ll.pop();
                }
                long time = System.nanoTime() - start;
                System.out.println("Average "+time/runs+" ns.");
            }
            • 3. Re: Searching most time-optimized java implementation of a stack
              796440
              Peter Lawrey wrote:
              btw @jverd, you might need to run it for longer, and you might find it even faster. ;)
              I enqueued and dequeued 100 million items. The enque took in the neighborhood of 5-6 sec. and the dequeue was around 1.5-2 sec.

              I'm not interested in the specific times myself. I just thought the OP's times sounded rather high, and he didn't provide any details about his test or about why he needs those particular numbers. I just wanted to draw him out to provide a little more information.
              • 4. Re: Searching most time-optimized java implementation of a stack
                823519
                Thank you everybody.

                In fact, because It is hard for me to read and write (and speak) english, I often forget to at least try to read the javadoc correctly. That's why I tried only the push, peek and pop methods, that are the most often typical of a stack. I'm sorry for that, and thank you again.

                best regards
                • 5. Re: Searching most time-optimized java implementation of a stack
                  802316
                  @jverd, it certainly was long enough. The only difference I guess is that I didn't create an object each time and didn't have a stack of more than one. A stack of 100 million may not be realistic either but shows how you test can change the results. The OP needs to test the functions he intends to use with a realistic data set (and size).
                  • 6. Re: Searching most time-optimized java implementation of a stack
                    796440
                    Peter Lawrey wrote:
                    @jverd, it certainly was long enough. The only difference I guess is that I didn't create an object each time
                    Neither did I.

                    (And I tested with 50 million items, not 100 million as I originally reported.)

                    Edited by: jverd on Dec 14, 2010 8:11 AM
                    • 7. Re: Searching most time-optimized java implementation of a stack
                      796440
                      user13067379 wrote:
                      Thank you everybody.

                      In fact, because It is hard for me to read and write (and speak) english, I often forget to at least try to read the javadoc correctly. That's why I tried only the push, peek and pop methods, that are the most often typical of a stack. I'm sorry for that, and thank you again.
                      Oops. My bad. I was looking at Queue, not Stack.

                      Using java.util.Stack, I got the following:
                      pushing 50,000,000 items took 3,844 ms, which is 0.076880 microseconds per item
                      popping 50,000,000 items took 2,562 ms, which is 0.051240 microseconds per item
                      pushing 50,000,000 items took 1,125 ms, which is 0.022500 microseconds per item
                      popping 50,000,000 items took 2,531 ms, which is 0.050620 microseconds per item
                      Edited by: jverd on Dec 14, 2010 8:12 AM