Incremental, but isolated grounding

[samutoljamo]

With gringo binary, it is possible to ground a program separately and use that as context while invoking Clingo. I.e. see the following programs:

% base.lp
% contains lots of rules and facts

% program1
% small program, creates typically a projection of the answer set, but not limited in any way

% program2
% small program, creates typically  a projection of the answer set, but no limited in any way

With the binaries, I can first ground base.lp, save that to a file and then invoke Clingo first for program1 and secondly for program2.

However, it seems to me that this behaviour is not possible using the C/C++ API. Is this indeed the case and will this be possible in Clingo 6?

Multi-shot solving / incremental grounding are not applicable, since the programs should be isolated. In our case, using externals to scope out the non-wanted programs won't also work. Creating a copy of the control object after grounding the base programs seems to be not possible. Forking the process may be possible, but seems like a hack rather than a solution.

I am aware of load_aspif, but would prefer avoiding file operations. Also, for larger programs, I am not sure if this would be possible via grounding observer API, but even if it is, it seems inefficient for the purpose.

[samutoljamo]

Also, this is partially related to #601

[rkaminsk]

This is directly possible using the API but not without file operations. You can

1. register an aspif backend
2. load the written file using load aspif

With clingo 6 you can now use clingo's internal text buffer to avoid file operations. There is one catch however, you can only access the non-preprocessed output via the text buffer, the preprocessed one can currently only be written to a file. I'll mark this as feature because it it is rather straightforward to add an option to write the preprocessed output to the text buffer as well.

[samutoljamo]

Thanks for the quick response! That seems much better. I am not familiar with Clingo's codebase, but I assume that copying the internal data structures would not be easy, since this has been explicitly prevented? I would guess that would be more performant than using ASPIF.

[rkaminsk]

The system does not support serialization as this would be rather complicated. The compromise is to replay the input via aspif. On Posix, forking might be interesting. Of course this falls short if you want to support windows.

[samutoljamo]

Yes, I think forking might then be the long-term solution for us and we likely won't need that level of performance for windows and thus it can remain a separate implementation for us, but as it would be separate implementation, it's not worth it to do now. Until Clingo 6, I think we'll use a statically linked fork of Clingo 5.8, since multi-threaded use requires the symbol table to use a RW-lock instead of a single mutex and this is quite easy to get with c++17. I assume that you won't accept this patch for Clingo 5, since it would require c++17? Anyway, thanks for the additions :)

[rkaminsk]

Yes, I think forking might then be the long-term solution for us and we likely won't need that level of performance for windows and thus it can remain a separate implementation for us, but as it would be separate implementation, it's not worth it to do now. Until Clingo 6, I think we'll use a statically linked fork of Clingo 5.8, since multi-threaded use requires the symbol table to use a RW-lock instead of a single mutex and this is quite easy to get with c++17. I assume that you won't accept this patch for Clingo 5, since it would require c++17? Anyway, thanks for the additions :)

I did not know that this makes such a performance difference. If it is important, we can also use a read write lock in the symbol table. On Posix, we have pthreads, which comes with pthread_rwlock_t. It should be easy to wrap this into a thin C++ wrapper similar to the C++17 classes. The fallback implementation can simply use a normal mutex.

[samutoljamo]

Yes, I think forking might then be the long-term solution for us and we likely won't need that level of performance for windows and thus it can remain a separate implementation for us, but as it would be separate implementation, it's not worth it to do now. Until Clingo 6, I think we'll use a statically linked fork of Clingo 5.8, since multi-threaded use requires the symbol table to use a RW-lock instead of a single mutex and this is quite easy to get with c++17. I assume that you won't accept this patch for Clingo 5, since it would require c++17? Anyway, thanks for the additions :)

I did not know that this makes such a performance difference. If it is important, we can also use a read write lock in the symbol table. On Posix, we have pthreads, which comes with pthread_rwlock_t. It should be easy to wrap this into a thin C++ wrapper similar to the C++17 classes. The fallback implementation can simply use a normal mutex.

I'll verify these tomorrow, but rough numbers on 14 cores running 14 parallel threads all running our grounding heavy programs seemed to be that grounding became ~10x slower per solve compared to using a single core. It was still faster overall, but the locking slowed down it very much. After using shared_lock(https://en.cppreference.com/w/cpp/thread/shared_lock.html) in symbol.cc(and upgrading it to unique-lock for the write), I think the per solve performance was quite close per solve performance using a single thread. However, would be nice to have the RW lock for windows too so it's a non-issue for us to use Clingo as a submodule with the patch and static linking has some additional benefits in this case too. Likely we're gonna need some form of #580 too so either I'll implement that or the fork system call way right away, since that would be only needed on POSIX

[rkaminsk]

I quickly patched in a shared mutex implementation. If this works for you, I could merge the PR. See #617.

[samutoljamo]

I will be able to test it tomorrow. Against a branch, which didn't have good perf tests, it was working though.

Btw, a bit related: I ran into some seg faults. However, I haven't been able to reproduce it now. It has only happened without this mutex: CyberismoCom/cyberismo@397c707 . I am suspecting refCount in astv2.h. See latest 3 commits here: https://github.com/samutoljamo/clingo/tree/fix

[samutoljamo]

Seems like I had stale builds when I said I can't reproduce the seg-fault, but I could after doing clean builds always. Anyway, a few tests.

With only seg-fault fix from my fork:

Running concurrent variant...
  concurrent run 1/5: 6834.0ms for 64 solves
  concurrent run 2/5: 6824.2ms for 64 solves
  concurrent run 3/5: 8480.0ms for 64 solves
  concurrent run 4/5: 12184.9ms for 64 solves
  concurrent run 5/5: 12546.5ms for 64 solves

Running sequential variant...
  sequential run 1/5: 7403.1ms for 64 solves
  sequential run 2/5: 6985.1ms for 64 solves
  sequential run 3/5: 7128.2ms for 64 solves
  sequential run 4/5: 8257.9ms for 64 solves
  sequential run 5/5: 6607.2ms for 64 solves
Results written to results-threading.json

With seg-fault fix + my RW lock with c++ 17:

Running concurrent variant...
  concurrent run 1/5: 3129.7ms for 64 solves
  concurrent run 2/5: 3283.8ms for 64 solves
  concurrent run 3/5: 3220.1ms for 64 solves
  concurrent run 4/5: 3154.7ms for 64 solves
  concurrent run 5/5: 3142.0ms for 64 solves

Running sequential variant...
  sequential run 1/5: 6543.8ms for 64 solves
  sequential run 2/5: 6393.8ms for 64 solves
  sequential run 3/5: 6573.1ms for 64 solves
  sequential run 4/5: 6446.6ms for 64 solves
  sequential run 5/5: 6335.1ms for 64 solves
Results written to results-threading.json

Your branch with the segfault fix cherry-picked:

Running concurrent variant...
  concurrent run 1/5: 3236.4ms for 64 solves
  concurrent run 2/5: 3243.5ms for 64 solves
  concurrent run 3/5: 3246.1ms for 64 solves
  concurrent run 4/5: 3297.7ms for 64 solves
  concurrent run 5/5: 3285.8ms for 64 solves

Running sequential variant...
  sequential run 1/5: 6616.0ms for 64 solves
  sequential run 2/5: 6529.1ms for 64 solves
  sequential run 3/5: 6628.2ms for 64 solves
  sequential run 4/5: 6327.7ms for 64 solves
  sequential run 5/5: 6370.6ms for 64 solves
Results written to results-threading.json

I am running tests on a different pc that is a bit more limited, here the speed benefit seems to be "only" 2x, allthough I confirmed that 14 cores are being used.

[samutoljamo]

Picking up a few single test runs:

Sync(runs via threadpool too, but js calls 1 by 1):

    {
      "method": "native",
      "feature": "threading",
      "variant": "sync",
      "project": "eucra",
      "cardCount": 205,
      "run": 5,
      "glueUs": 446,
      "addUs": 8511,
      "groundUs": 83073,
      "solveUs": 2298,
      "totalUs": 94328,
      "cacheHit": false
    },

Async(runs via threadpool with js queueing jobs at the same time):

    {
      "method": "native",
      "feature": "threading",
      "variant": "async",
      "project": "eucra",
      "cardCount": 205,
      "run": 1,
      "glueUs": 564,
      "addUs": 54684,
      "groundUs": 1117690,
      "solveUs": 4662,
      "totalUs": 1177600,
      "cacheHit": false
    },

Something seems to be still slowing down the grounding if there are multiple grounds happening parallel

[rkaminsk]

The AST has actually not been written with thread safety in mind. And I think there is a bug in your code. You need a fence:

    if (ast_->decRef()) {
        // you need a fence here otherwise memory might be reordered (probably only affects ARM)
        std::atomic_thread_fence(std::memory_order_acquire);
        delete ast_;
    }

Since I did not think about thread safety when writing the AST I am not sure this is the only place one has to safe guard.