implementing debounce in Java

Question

For some code I'm writing I could use a nice general implementation of debounce in Java.

public interface Callback {
  public void call(Object arg);
}

class Debouncer implements Callback {
    public Debouncer(Callback c, int interval) { ... }

    public void call(Object arg) { 
        // should forward calls with the same arguments to the callback c
        // but batch multiple calls inside `interval` to a single one
    }
}

When call() is called multiple times in interval milliseconds with the same argument the callback function should be called exactly once.

A visualization:

Debouncer#call  xxx   x xxxxxxx        xxxxxxxxxxxxxxx
Callback#call      x           x                      x  (interval is 2)

• Does (something like) this exist already in some Java standard library?
• How would you implement that?

Heptavalent

looks like java.util.concurrency provides the building blocks – Heptavalent

I know this is an old question, but I posted a similar question a few months ago here: #18723612 and provided a reusable implementation on GitHub that might be of interest – Storage

Answer 1

Please consider the following thread safe solution. Note that the lock granularity is on the key level, so that only calls on the same key block each other. It also handles the case of an expiration on key K which occurs while call(K) is called.

public class Debouncer <T> {
  private final ScheduledExecutorService sched = Executors.newScheduledThreadPool(1);
  private final ConcurrentHashMap<T, TimerTask> delayedMap = new ConcurrentHashMap<T, TimerTask>();
  private final Callback<T> callback;
  private final int interval;

  public Debouncer(Callback<T> c, int interval) { 
    this.callback = c;
    this.interval = interval;
  }

  public void call(T key) {
    TimerTask task = new TimerTask(key);

    TimerTask prev;
    do {
      prev = delayedMap.putIfAbsent(key, task);
      if (prev == null)
        sched.schedule(task, interval, TimeUnit.MILLISECONDS);
    } while (prev != null && !prev.extend()); // Exit only if new task was added to map, or existing task was extended successfully
  }
  
  public void terminate() {
    sched.shutdownNow();
  }
  
  // The task that wakes up when the wait time elapses
  private class TimerTask implements Runnable {
    private final T key;
    private long dueTime;    
    private final Object lock = new Object();

    public TimerTask(T key) {        
      this.key = key;
      extend();
    }

    public boolean extend() {
      synchronized (lock) {
        if (dueTime < 0) // Task has been shutdown
          return false;
        dueTime = System.currentTimeMillis() + interval;
        return true;
      }
    }
      
    public void run() {
      synchronized (lock) {
        long remaining = dueTime - System.currentTimeMillis();
        if (remaining > 0) { // Re-schedule task
          sched.schedule(this, remaining, TimeUnit.MILLISECONDS);
        } else { // Mark as terminated and invoke callback
          dueTime = -1;
          try {
            callback.call(key);
          } finally {
            delayedMap.remove(key);
          }
        }
      }
    }  
  }

and callback interface:

public interface Callback<T> {
    public void call(T t);
}

Semivitreous

@levinalex: just fixed a bug in call(..). The loop was added to make sure that we never have a scheduled task that's not in the map. – Semivitreous

Eyal, I have a question. let's say the interval is 5 seconds.. if a call is invoked every 3 seconds, the callback will never run. right? – Sweeper

@AlexanderSuraphel: That's correct. Assuming you use the same key, the execution time will be delayed over and over again. – Semivitreous

You should add catch after the try block because any exception will cancel the callback called on debounce – Meltage

another thing to note is that ` callback.call(key);` is called in the background thread – Meltage

@Angelina: What kind of behavior would you expect when the caller provides a faulty callback? note that: 1) No functionality is broken, and only the specific faulty callback won't be fully executed. 2) This is a very basic implementation - you can enhance it by allowing the caller to set an error handler, or by logging the error, etc. – Semivitreous

How to use this class ? – Melendez

Answer 2

Here's my implementation:

public class Debouncer {
    private final ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
    private final ConcurrentHashMap<Object, Future<?>> delayedMap = new ConcurrentHashMap<>();

    /**
     * Debounces {@code callable} by {@code delay}, i.e., schedules it to be executed after {@code delay},
     * or cancels its execution if the method is called with the same key within the {@code delay} again.
     */
    public void debounce(final Object key, final Runnable runnable, long delay, TimeUnit unit) {
        final Future<?> prev = delayedMap.put(key, scheduler.schedule(new Runnable() {
            @Override
            public void run() {
                try {
                    runnable.run();
                } finally {
                    delayedMap.remove(key);
                }
            }
        }, delay, unit));
        if (prev != null) {
            prev.cancel(true);
        }
    }

    public void shutdown() {
        scheduler.shutdownNow();
    }
}

Example usage:

final Debouncer debouncer = new Debouncer();
debouncer.debounce(Void.class, new Runnable() {
    @Override public void run() {
        // ...
    }
}, 300, TimeUnit.MILLISECONDS);

Stinky

Answer 3

I don't know if it exists but it should be simple to implement.

class Debouncer implements Callback {

  private CallBack c;
  private volatile long lastCalled;
  private int interval;

  public Debouncer(Callback c, int interval) {
     //init fields
  }

  public void call(Object arg) { 
      if( lastCalled + interval < System.currentTimeMillis() ) {
        lastCalled = System.currentTimeMillis();
        c.call( arg );
      } 
  }
}

Of course this example oversimplifies it a bit, but this is more or less all you need. If you want to keep separate timeouts for different arguments, you'll need a Map<Object,long> instead of just a long to keep track of the last execution time.

Jase

What I need is the opposite. the callback should be called at the end of every bunch of calls. (I want to use it to implement this) Which seems to require Threads/Timeouts – Heptavalent

@Heptavalent I still think you could make it work this way but if you don't, don't use threads, use Timer or ScheduledExecutorService instead, it's much cleaner and safer that way. – Jase

Thanks for these. I'm trying to make that work right now. (I've never done Java concurrency before) – Heptavalent

Timers seem to be exactly what I need. – Heptavalent

Answer 4

My implementation, very easy to use, 2 util methods for debounce and throttle, pass your runnable into it to get the debounce/throttle runnable

package basic.thread.utils;

public class ThreadUtils {
    /** Make a runnable become debounce
     * 
     * usage: to reduce the real processing for some task
     * 
     * example: the stock price sometimes probably changes 1000 times in 1 second,
     *  but you just want redraw the candlestick of k-line chart after last change+"delay ms"
     * 
     * @param realRunner Runnable that has something real to do
     * @param delay milliseconds that realRunner should wait since last call
     * @return
     */
    public static Runnable debounce (Runnable realRunner, long delay) {
        Runnable debounceRunner = new Runnable() {
            // whether is waiting to run
            private boolean _isWaiting = false;
            // target time to run realRunner
            private long _timeToRun;
            // specified delay time to wait
            private long _delay = delay;
            // Runnable that has the real task to run
            private Runnable _realRunner = realRunner;
            @Override
            public void run() {
                // current time
                long now;
                synchronized (this) {
                    now = System.currentTimeMillis();
                    // update time to run each time
                    _timeToRun = now+_delay;
                    // another thread is waiting, skip
                    if (_isWaiting) return;
                    // set waiting status
                    _isWaiting = true;
                }
                try {
                    // wait until target time
                    while (now < _timeToRun) {
                        Thread.sleep(_timeToRun-now);
                        now = System.currentTimeMillis();
                    }
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    // clear waiting status before run
                    _isWaiting = false;
                    // do the real task
                    _realRunner.run();
                }
            }};
        return debounceRunner;
    }
    /** Make a runnable become throttle
     * 
     * usage: to smoothly reduce running times of some task
     * 
     * example: assume the price of a stock often updated 1000 times per second
     * but you want to redraw the candlestick of k-line at most once per 300ms
     * 
     * @param realRunner
     * @param delay
     * @return
     */
    public static Runnable throttle (Runnable realRunner, long delay) {
        Runnable throttleRunner = new Runnable() {
            // whether is waiting to run
            private boolean _isWaiting = false;
            // target time to run realRunner
            private long _timeToRun;
            // specified delay time to wait
            private long _delay = delay;
            // Runnable that has the real task to run
            private Runnable _realRunner = realRunner;
            @Override
            public void run() {
                // current time
                long now;
                synchronized (this) {
                    // another thread is waiting, skip
                    if (_isWaiting) return;
                    now = System.currentTimeMillis();
                    // update time to run
                    // do not update it each time since
                    // you do not want to postpone it unlimited
                    _timeToRun = now+_delay;
                    // set waiting status
                    _isWaiting = true;
                }
                try {
                    Thread.sleep(_timeToRun-now);

                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    // clear waiting status before run
                    _isWaiting = false;
                    // do the real task
                    _realRunner.run();
                }
            }};
        return throttleRunner;
    }
}

Playsuit

Answer 5

Here is my implementation, Java:

SimpleDebounce.java

import android.os.Handler;

public class SimpleDebounce {
    protected Handler handler;
    protected IAfterDelay iAfterDelay;
    protected long last_time_invoke = 0;
    protected long delay;

    public SimpleDebounce() {
        this.handler = new Handler();
    }

    public SimpleDebounce(long delay, IAfterDelay iAfterDelay) {
        this();
        this.delay = delay;
        this.iAfterDelay = iAfterDelay;
    }

    public void after(long delay, IAfterDelay iAfterDelay) {
        this.delay = delay;
        this.iAfterDelay = iAfterDelay;
        this.iAfterDelay.loading(true);
        this.handler.removeCallbacks(execute);
        this.last_time_invoke = System.currentTimeMillis();
        this.handler.postDelayed(execute, delay);
    }

    public void cancelDebounce() {
        if (handler != null && iAfterDelay != null) {
            handler.removeCallbacks(execute);
            iAfterDelay.loading(false);
        }
    }

    public interface IAfterDelay {
        void fire();

        void loading(boolean state);
    }

    protected Runnable execute = () -> {
        if (System.currentTimeMillis() > (last_time_invoke + delay - 500)) {
            if (iAfterDelay != null) {
                iAfterDelay.loading(false);
                iAfterDelay.fire();
            }
        }
    };

}

MainActivity.java

public class MainActivity extends AppCompatActivity {

   private SimpleDebounce simpleDebounce;
   private long waitForMS = 5000;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_my_stocks);

        simpleDebounce = new SimpleDebounce();

        // You can click this button as many time as you want
        // It will reset the time and fire after ${waitForMS} milisecons
        // and in case you pressed this in the middle again, it will reset the time
        someButtonWhichStartsThis.setOnClickListener(e -> {
           simpleDebounce.after(waitForMS, new SimpleDebounce.IAfterDelay() {
                @Override
                public void fire() {
                   // Your job...
                }

                @Override
                public void loading(boolean state) {
                    if (state) turnOnProgress();
                    else turnOffProgress();
                }
          });
        });

        // stop the future fire in the middle, if you want to
        someButtonWhichStopsThis.setOnClickListener(e -> simpleDebounce.cancelDebounce());

    }
   

}

Wintery

Answer 6

This looks like it could work:

class Debouncer implements Callback {
    private Callback callback;
    private Map<Integer, Timer> scheduled = new HashMap<Integer, Timer>();
    private int delay;

    public Debouncer(Callback c, int delay) {
        this.callback = c;
        this.delay = delay;
    }

    public void call(final Object arg) {
        final int h = arg.hashCode();
        Timer task = scheduled.remove(h);
        if (task != null) { task.cancel(); }

        task = new Timer();
        scheduled.put(h, task);

        task.schedule(new TimerTask() {
            @Override
            public void run() {
                callback.call(arg);
                scheduled.remove(h);
            }
        }, this.delay);
    }
}

Heptavalent

Do you ever add the object to the hash map? And also, you should never use hashCode as the key, because it will easily create collisions. Not to mention that objects of different type will easily have equal hash codes, even if their own hash functions are perfect. – Shiite

fixed the answer to actually schedule things. What would I use instead of hashCode? – Heptavalent

Simply use the actual object as the key (I.e. Map<Object, Timer>). HashMap then uses the object's hash code internally to quickly jump to the bucket containing your item (and potentially other items with the same hash code), but after that the hash code is ignored and it compares the actual Object with ones in that bucket to find the matching one. Tldr; whenever you call hashCode() in your code, you are most likely doing something wrong. – Shiite

-1 This solution is not thread safe, and even for one thread it fails to meet the requirements. As Groo claims, different args with the same hashcode will cancel each others tasks. In addition, the creation of multiple timers is not efficient and unnecessary. – Semivitreous

people should probably use the solution given in #18723612 instead of my hacked attempt. I don't really know Java. – Heptavalent

Answer 7

The following implementation works on Handler based threads (e.g. the main UI thread, or in an IntentService). It expects only to be called from the thread on which it is created, and it will also run it's action on this thread.

public class Debouncer
{
    private CountDownTimer debounceTimer;
    private Runnable pendingRunnable;

    public Debouncer() {

    }

    public void debounce(Runnable runnable, long delayMs) {
        pendingRunnable = runnable;
        cancelTimer();
        startTimer(delayMs);
    }

    public void cancel() {
        cancelTimer();
        pendingRunnable = null;
    }

    private void startTimer(final long updateIntervalMs) {

        if (updateIntervalMs > 0) {

            // Debounce timer
            debounceTimer = new CountDownTimer(updateIntervalMs, updateIntervalMs) {

                @Override
                public void onTick(long millisUntilFinished) {
                    // Do nothing
                }

                @Override
                public void onFinish() {
                    execute();
                }
            };
            debounceTimer.start();
        }
        else {

            // Do immediately
            execute();
        }
    }

    private void cancelTimer() {
        if (debounceTimer != null) {
            debounceTimer.cancel();
            debounceTimer = null;
        }
    }

    private void execute() {
        if (pendingRunnable != null) {
            pendingRunnable.run();
            pendingRunnable = null;
        }
    }
}

Michelle

Answer 8

Here is my working implementation:

Execution Callback:

public interface cbDebounce {

void execute();

}

Debouncer:

public class Debouncer {

private Timer timer;
private ConcurrentHashMap<String, TimerTask> delayedTaskMap;

public Debouncer() {
    this.timer = new Timer(true); //run as daemon
    this.delayedTaskMap = new ConcurrentHashMap<>();
}

public void debounce(final String key, final cbDebounce debounceCallback, final long delay) {
    if (key == null || key.isEmpty() || key.trim().length() < 1 || delay < 0) return;

    cancelPreviousTasks(); //if any

    TimerTask timerTask = new TimerTask() {
        @Override
        public void run() {
            debounceCallback.execute();
            cancelPreviousTasks();
            delayedTaskMap.clear();
            if (timer != null) timer.cancel();
        }
    };

    scheduleNewTask(key, timerTask, delay);
}

private void cancelPreviousTasks() {
    if (delayedTaskMap == null) return;

    if (!delayedTaskMap.isEmpty()) delayedTaskMap
            .forEachEntry(1000, entry -> entry.getValue().cancel());

    delayedTaskMap.clear();
}

private void scheduleNewTask(String key, TimerTask timerTask, long delay) {
    if (key == null || key.isEmpty() || key.trim().length() < 1 || timerTask == null || delay < 0) return;

    if (delayedTaskMap.containsKey(key)) return;

    timer.schedule(timerTask, delay);

    delayedTaskMap.put(key, timerTask);
}

}

Main (to test)

public class Main {

private static Debouncer debouncer;

public static void main(String[] args) throws IOException, InterruptedException {
    debouncer = new Debouncer();
    search("H");
    search("HE");
    search("HEL");
    System.out.println("Waiting for user to finish typing");
    Thread.sleep(2000);
    search("HELL");
    search("HELLO");
}

private static void search(String searchPhrase) {
    System.out.println("Search for: " + searchPhrase);
    cbDebounce debounceCallback = () -> System.out.println("Now Executing search for: "+searchPhrase);
    debouncer.debounce(searchPhrase, debounceCallback, 4000); //wait 4 seconds after user's last keystroke
}

}

Output

• Search for: H
• Search for: HE
• Search for: HEL
• Waiting for user to finish typing
• Search for: HELL
• Search for: HELLO
• Now Executing search for: HELLO

Eleemosynary

Answer 9

I've updated @Eyal's answer to be able to configure debouncing time in each call, and use runnable code block instead of callback:

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class Debouncer<T> {

    private final ScheduledExecutorService sched = Executors.newScheduledThreadPool(1);
    private final ConcurrentHashMap<T, TimerTask> delayedMap = new ConcurrentHashMap<T, TimerTask>();

    public Debouncer() {
    }

    public void call(T key, Runnable runnable, int interval, TimeUnit timeUnit) {
        TimerTask task = new TimerTask(key, runnable, interval, timeUnit);

        TimerTask prev;
        do {
            prev = delayedMap.putIfAbsent(key, task);
            if (prev == null)
                sched.schedule(task, interval, timeUnit);
        } while (prev != null && !prev.extend());
    }

    public void terminate() {
        sched.shutdownNow();
    }

    private class TimerTask implements Runnable {
        private final T key;
        private final Runnable runnable;
        private final int interval;
        private final TimeUnit timeUnit;
        private long dueTime;
        private final Object lock = new Object();

        public TimerTask(T key, Runnable runnable, int interval, TimeUnit timeUnit) {
            this.key = key;
            this.runnable = runnable;
            this.interval = interval;
            this.timeUnit = timeUnit;
            extend();
        }

        public boolean extend() {
            synchronized (lock) {
                if (dueTime < 0)
                    return false;
                dueTime = System.currentTimeMillis() + TimeUnit.MILLISECONDS.convert(interval, timeUnit);
                return true;
            }
        }

        public void run() {
            synchronized (lock) {
                long remaining = dueTime - System.currentTimeMillis();
                if (remaining > 0) { // Re-schedule task
                    sched.schedule(this, remaining, TimeUnit.MILLISECONDS);
                } else { // Mark as terminated and invoke callback
                    dueTime = -1;
                    try {
                        runnable.run();
                    } finally {
                        delayedMap.remove(key);
                    }
                }
            }
        }
    }
}

Roscoe