alpha-asp/Alpha

Investigate ArrayList for watches

lorenzleutgeb opened this issue · 2 comments

lorenzleutgeb commented

Because the following involves benchmarking, it might warrant a separat issue, but nevertheless, I uncovered it during the review for #274, so here we go:

C:\Users\lorenz\src\github.com\alpha-asp\Alpha\alpha-core\src\main\java\at\ac\tuwien\kr\alpha\core\solver\NoGoodStoreAlphaRoaming.java:78: warning: [rawtypes] found raw type: ArrayList
	private ArrayList<WatchedNoGood>[] watches = new ArrayList[0];
	                                                 ^
  missing type arguments for generic class ArrayList<E>
  where E is a type-variable:
    E extends Object declared in class ArrayList
...

These warnings can be avoided by using ArrayList<ArrayList<WatchedNoGood>> instead of ArrayList<WatchedNoGood>[]. It's not obvious how the two variants differ in performance, so I'd ask for benchmarking, but at the same time I conjecture that the impact would be neglegible.

Agreed, this should not be changed without benchmarking. Since access to watches is at the core of propagation, this is (part of) the code that runs millions of times per second. Arrays have a small advantage over ArrayLists, namely that the array (in theory) needs only one memory access to get the desired data, while the ArrayList is an object that stores a reference to an array, hence there are two memory accesses required to get the data. Since the outer list is accessed randomly (while the inner one will be walked sequentially), I conjecture that changing the outer to an ArrayList might slow down propagation. But at the moment, I also do not have solid data for that behaviour with the current solver. For the moment a separate issue might be advised.

Originally posted by @AntoniusW in #300 (comment)

lorenzleutgeb commented

OK, so here's the separate issue 😄

I get your argument, but I wouldn't be surprised if modern Java JITs could optimize that...

AntoniusW commented

OK, so here's the separate issue smile

I get your argument, but I wouldn't be surprised if modern Java JITs could optimize that...

Thanks. It would not surprise me either. Indeed, there is some very interesting work on JIT object inlining (cf. https://ssw.jku.at/Research/Papers/Wimmer08PhD/Wimmer08PhD.pdf) that might do precisely what is done manually here. Nevertheless, I would like to be sure that there is no negative impact before proceeding.

  • 👍1