Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a library which makes HTTP calls to my service. I was trying to calculate running average of how much time my service is taking on an average.

Here is the core logic of how I am calculating "running average":

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.LinkedList;
import java.util.Queue;

public class MovingAverage {

    private final Queue<BigDecimal> window = new LinkedList<BigDecimal>();
    private final int period;
    private BigDecimal sum = BigDecimal.ZERO;

    public MovingAverage(int period) {
        this.period = period;
    }

    public void add(BigDecimal num) {
        sum = sum.add(num);
        window.add(num);
        if (window.size() > period) {
            sum = sum.subtract(window.remove());
        }
    }

    public BigDecimal getAverage() {
        if (window.isEmpty()) return BigDecimal.ZERO;
        BigDecimal divisor = BigDecimal.valueOf(window.size());
        return sum.divide(divisor, 2, RoundingMode.HALF_UP);
    }
}

Is there any better/optimized way to do the same thing? I want to make sure this running average calculation is fast since this library runs under very heavy load so this should not increase the overall latency.

share|improve this question
    
Are you on Java 8? And do you need thread safety? – h.j.k. May 5 at 3:05
    
I am on Java 7 (cannot move to java 8 yet) and yeah I need thread safety because this method will be called from multithreaded code. – david May 5 at 3:05
2  
Do you really need BigDecimal? What's wrong with double? – 200_success May 5 at 3:23
    
I thought there might be some big outliers so that's why I went that way but thinking more on this double would be more suited here. Thanks for suggestion. – david May 5 at 5:20

Your code looks nice and seems to do exactly what is supposed to be done. I can suggest only one performance related improvement: change LinkedList to ArrayDeque. Don't let the prefix Array scare you: operations add() and remove() are implemented that way that they run in amortized contant time.

I have compared the performance of the both variants (LinkedList versus ArrayDeque):

MovingAverage (with LinkedList) in 1808.1 milliseconds.
MovingAverageV2 (with ArrayDeque) in 1480.6 milliseconds.

Plus, I have a minor comment. Since Java 7, you can write simply

new LinkedList<>();

instead of

new LinkedList<BigDecimal>();

The above syntax sugar is called diamond inference.

Hope that helps.

(PS: If you want to run the performance demonstration, you can find everything needed here.)

share|improve this answer
1  
To clarify, the reason ArrayDeque is faster is memory locality. LinkedList.getLast() is O(1) but because the elements aren't near each other in memory you get more cache hits with ArrayDeque. – JonathanR May 5 at 13:13
    
Exactly! Note also that adding a new element to LinkedList creates a linked list node behind the scene, and that's expensive since it dives into JVM and possibly to kernel from there. Also, when you remove an element, its node becomes garbage and that's more work for garbage collector. – coderodde May 5 at 13:34
    
Thanks a lot for your suggestion. I didn't know about ArrayDeque so I learned something today. Also do you think I should switch to start using double instead of BigDecimal? – david May 5 at 20:01
    
double s are less accurate than BigDecimal , yet more efficient. The answer depends on the concrete use-case. – coderodde May 5 at 20:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.