Hi all!
Lately I've noticed that the "-l good-intentions" preset took longer to solve
the Microsoft 32,000. After some investigation, I discovered that this was
caused by the fact that good-intention now actually respects the
"--next-instance" flag and runs an atomic moves preset if the meta-moves one
fails, which causes a significant slowdown overall. So from now on I'm going
to use "-l cj" (which is good-intentions' meta-moves preset) to test the MS
32,000.
I've also decided to run the same benchmark (./configure with a "release"
build and with the MS 32,000 on -l cj) on the various releases of Freecell
Solver. Here are the results (in seconds):
{{{{{{{{{{
2.12: 138.151165008545
2.14: 138.430589914322
2.16: 138.160212039948
2.18: 145.739367961884
2.20: 211.631674051285
2.22: 217.067227840424
2.24: 222.523734092712
2.26: 188.568401098251
2.28: 162.522223949432
2.30: 155.830921888351
2.32: 161.899503946304
2.34: 146.585238218307
}}}}}}}}}
As one can see there is a significant slowdown between 2.18.x and 2.20.x. This
is relatively surprising considering that the only change there was this:
{{{{{{{{{{{{{{{{{{{{{{
Index: fc-solve/source/intrface.c
===================================================================
--- fc-solve/source/intrface.c (.../2.18.0) (revision 2164)
+++ fc-solve/source/intrface.c (.../2.20.0) (revision 2164)
_at__at_ -1398,6 +1398,23 _at__at_
/***********************************************************/
+static void finish_hard_thread(
+ fc_solve_hard_thread_t * hard_thread
+ )
+{
+ fc_solve_state_ia_finish(hard_thread);
+
+#ifdef INDIRECT_STACK_STATES
+ fc_solve_compact_allocator_finish(hard_thread->stacks_allocator);
+ hard_thread->stacks_allocator = NULL;
+#endif
+
+ fc_solve_compact_allocator_finish(hard_thread->move_stacks_allocator);
+ hard_thread->move_stacks_allocator = NULL;
+
+ return;
+}
+
/*
This function should be called after the user has retrieved the
results generated by the scan as it will destroy them.
_at__at_ -1407,7 +1424,6 _at__at_
)
{
int ht_idx;
- fc_solve_hard_thread_t * hard_thread;
#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)
free(instance->indirect_prev_states);
_at__at_ -1416,21 +1432,12 _at__at_
/* De-allocate the state packs */
for(ht_idx=0;ht_idx<instance->num_hard_threads;ht_idx++)
{
- hard_thread = instance->hard_threads[ht_idx];
- fc_solve_state_ia_finish(hard_thread);
-
-#ifdef INDIRECT_STACK_STATES
- fc_solve_compact_allocator_finish(hard_thread->stacks_allocator);
- hard_thread->stacks_allocator = NULL;
-#endif
- fc_solve_compact_allocator_finish(hard_thread-
>move_stacks_allocator);
- hard_thread->move_stacks_allocator = NULL;
-
+ finish_hard_thread(instance->hard_threads[ht_idx]);
}
if (instance->optimization_thread)
{
- fc_solve_state_ia_finish(instance->optimization_thread);
+ finish_hard_thread(instance->optimization_thread);
}
_at__at_ -1570,13 +1577,42 _at__at_
return ret->soft_threads[0];
}
+static void recycle_hard_thread(
+ fc_solve_hard_thread_t * hard_thread
+ )
+{
+ int st_idx;
+ fc_solve_soft_thread_t * soft_thread;
+
+ hard_thread->num_times = 0;
+ hard_thread->ht_max_num_times = hard_thread->num_times_step;
+ hard_thread->max_num_times = -1;
+ hard_thread->num_soft_threads_finished = 0;
+ hard_thread->move_stacks_allocator =
+ fc_solve_compact_allocator_new();
+#ifdef INDIRECT_STACK_STATES
+ hard_thread->stacks_allocator =
+ fc_solve_compact_allocator_new();
+#endif
+ for(st_idx = 0; st_idx < hard_thread->num_soft_threads ; st_idx++)
+ {
+ soft_thread = hard_thread->soft_threads[st_idx];
+ soft_thread->is_finished = 0;
+ soft_thread->initialized = 0;
+
+ fc_solve_rand_srand(soft_thread->rand_gen, soft_thread->rand_seed);
+ /* Reset the priority queue */
+ soft_thread->a_star_pqueue->CurrentSize = 0;
+ }
+
+ return;
+}
+
void fc_solve_recycle_instance(
fc_solve_instance_t * instance
)
{
- int ht_idx, st_idx;
- fc_solve_hard_thread_t * hard_thread;
- fc_solve_soft_thread_t * soft_thread;
+ int ht_idx;
fc_solve_finish_instance(instance);
_at__at_ -1586,26 +1622,21 _at__at_
for(ht_idx = 0; ht_idx < instance->num_hard_threads; ht_idx++)
{
- hard_thread = instance->hard_threads[ht_idx];
- hard_thread->num_times = 0;
- hard_thread->ht_max_num_times = hard_thread->num_times_step;
- hard_thread->max_num_times = -1;
- hard_thread->num_soft_threads_finished = 0;
- hard_thread->move_stacks_allocator =
- fc_solve_compact_allocator_new();
-#ifdef INDIRECT_STACK_STATES
- hard_thread->stacks_allocator =
- fc_solve_compact_allocator_new();
+ recycle_hard_thread(instance->hard_threads[ht_idx]);
+ }
+ /*
+ For the time being instance->optimization_thread must be NULL when
+ the solution has started. Else, it breaks the internal code's
+ expectations.
+ */
+#if 0
+ recycle_hard_thread(instance->optimization_thread);
+#else
+ if (instance->optimization_thread)
+ {
+ free_instance_hard_thread_callback(instance->optimization_thread);
+ instance->optimization_thread = NULL;
+ }
#endif
- for(st_idx = 0; st_idx < hard_thread->num_soft_threads ; st_idx++)
- {
- soft_thread = hard_thread->soft_threads[st_idx];
- soft_thread->is_finished = 0;
- soft_thread->initialized = 0;
+}
- fc_solve_rand_srand(soft_thread->rand_gen, soft_thread-
>rand_seed);
- /* Reset the priority queue */
- soft_thread->a_star_pqueue->CurrentSize = 0;
- }
- }
-}
}}}}}}}}}}}}}}}}}}}}}}
As one can see, I just extracted a few functions. Now I'm going to try to
inline them and see how it goes.
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
What Makes Software Apps High Quality - http://xrl.us/bkeuk
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Sun Jul 26 2009 - 01:14:22 IDT