Hi all!
There is a new and faster hash table-based backend for the depth-dbm solver
based on
https://apr.apache.org/ 's
https://apr.apache.org/docs/apr/1.7/group__apr__hash.html .
Some benchmarks:
Before:
shlomif[0fc]:$this$ time bash run-job-1.bash 618759589
Trying deal = 618759589
Trying deal = 618759589 using dbm
^X_at_snmFinished running threads for curr_depth=103
Start mark-and-sweep cleanup for curr_depth=103
Finish mark-and-sweep cleanup for curr_depth=103
instance_run_all_threads end
handle_and_destroy_instance_solution start
Reached 32000000 ; States-in-collection: 35817072 ; Time: 1559155303.282119
>>>Queue Stats: inserted=35817072 items_in_queue=3817072 extracted=32000000
Intractable.
Reached Max-or-more iterations of 32000000.
handle_and_destroy_instance_solution end
bash run-job-1.bash 618759589 277.00s user 0.82s system 99% cpu 4:37.83
total
After:
shlomif[0fc]:$this$ time bash run-job-1.bash 618759589
Trying deal = 618759589
Trying deal = 618759589 using dbm
instance_run_solver_thread start
instance_run_solver_thread end
Finished running threads for curr_depth=103
instance_run_all_threads end
handle_and_destroy_instance_solution start
Reached 32000000 ; States-in-collection: 35817072 ; Time: 1559383115.221818
>>>Queue Stats: inserted=35817072 items_in_queue=3817072 extracted=32000000
Intractable.
Reached Max-or-more iterations of 32000000.
bash run-job-1.bash 618759589 156.54s user 1.48s system 108% cpu 2:25.01
total
--------
This is largely thanks to a freenode conversation with
http://adtinfo.org/
who stressed the fact that hashes performed better than binary trees
usually. The downside of this hash backend is that it consumes much more
RAM. Note that there is a compile-time choice of either backend.
The dbm solver still seems much slower than fc-solve though.
--
Shlomi Fish http://www.shlomifish.org/
Buddha has the Chuck Norris nature.
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Sun Jun 09 2019 - 11:47:15 IDT