Android Rubik's Cube Kociemba optimal solver memory shortage

Question

It may be a bit late, but I was also facing this issue quite recently when I was working on a Rubik's-Cube-solving-robot using an Android-Smartphone for scanning the cube and computing the solution, so I'll put here what I have found out.

What is the problem?

Let's start off by discussing where the problem causing that performance issue actually is located.

The reason for that being so slow is the class CoordCube, which looks (very simplified) like this:

class CoordCube {
    short[] pruneTables;

    static {
        /* compute and save ~50MB data in `pruneTables` */
    }
}

Basically what it does, is to load a pretty big amount of data into lookup-tables which are required for a fast solving procedure. This loading is automatically executed by the JVM once this class is first instantiated. That happens on line 159 in Search.solution():

/* simplified code of solution() */
if (cube.isValid()) {
    CoordCube c = new CoordCube(); // pruning tables will be loaded on this line

That is also the reason why this method executes in negligible time as long as the passed cube is invalid, since it never gets to load the tables.

Possible Solutions:

Now that we have identified where the problem is located, let's focus on how to solve it.

I have come up with 3 different approaches, where the first one is probably the easiest (but also the slowest execution wise ...) and is also used in my App. The other two are just ideas on how to improve the performance even more.

Approach 1:

The first and most simple approach is to just manually preload the lookup tables in a kind of LoadingActivity with a ProgressBar showing our current progress. For that we first want to be able to manually control exactly when which tables are loaded (when the class is first instantiated is not precise enough), like this:

loadTable1() {
     /* load pruning table number 1 */
}

For that I have written some simple utility here (code is too long to paste). Make sure to check out my instructions there on how to properly import that code in your App.

Also we will probably want to do the loading in the background, namely in an AsyncTask. This is how I have done it in my application (PruneTableLoader is included in the previous link):

private class LoadPruningTablesTask extends AsyncTask<Void, Void, Void> {
    private PruneTableLoader tableLoader = new PruneTableLoader();

    @Override
    protected Void doInBackground(Void... params) {
        /* load all tables if they are not already in RAM */
        while (!tableLoader.loadingFinished()) { // while tables are left to load
            tableLoader.loadNext(); // load next pruning table
            publishProgress(); // increment `ProgressBar` by one
        }

        return null;
    }

    @Override
    protected void onProgressUpdate(Void... values) {
        super.onProgressUpdate(values);
        /* increment `ProgressBar` by 1 */
    }
}

When using my PruneTableLoader, the loading of all tables needs about 40s on my Samsung Galaxy S3 with 250 MB RAM free. (in contrast it needs well over 2min when loading them automatically and in addition often results in a crash ...)

That may still sound quite slow considering it needs < 1s on PC, but at least you must only do that once, since Android caches the static-variables and you so don't have to load them on every startup of your App.

Approach 2: (untested)

I assume it would be faster to save the pruning tables in a file or a database and load them from there instead of always recomputing them. I have not yet tested that though and it will probably require quite some work getting the saving and loading to work properly. (also maybe it's not even faster because of access times)

Approach 3: (untested)

Well, the hardest and also by decades most work expensive solution would be, to simply rewrite the whole algorithm in C or C++ and invoke it in the App via JNI. (Herbert Kociemba has not published his C-sourcecode yet as far as I know ...)

This is going to be the performance wise fastest solution for sure. (also for the solving procedure itself)

All in all approach 1 is probably the effort/benefit-wise best approach for the beginning (and also was for me), so I would recommend you to go with that, in case the loading time is not such a huge issue for your Application.

I'm not completely satisfied with the performance of that myself though, so I may try out approach 2 and maybe even approach 3 some time in the future. In case I do that, I will update this post with my results then.