Title space improvement for LM-Count
Priority feature Status resolved
Superseder Nosy List jendrik, malte, manuel, salome
Assigned To Keywords
Optional summary

Created on 2016-12-14.15:43:20 by jendrik, last changed by salome.

msg7441 (view) Author: salome Date: 2018-09-13.17:26:29
We merged the code, but afterwards discovered a bug which leads to incorrect
behaviour for all landmark configurations which use the method
convert_to_landmark_set(). This did not show up in the experiments since bjolp
does not use this method.

We fixed the bug in default and ran lama-first as a sanity check:

There are still some instances where the evaluations differ but this is most
likely explained with issue383.

If you want to see the fix, see We
will close the issue now, if you want to take another look you can open it again.
msg7421 (view) Author: malte Date: 2018-09-13.11:44:31
Great! The experiments look excellent. Do you want someone to look at the code
again, or should we merge this immediately?
msg7420 (view) Author: salome Date: 2018-09-13.11:14:54
Jendrik and I just looked into the memory usage of 32bit blind search since it
seemed weird that we save memory there. The memory savings can be explained with
the binary size: the 32bit base version is 6240784 bytes and the 32bit v2
version only 3540836 btyes.
msg7419 (view) Author: salome Date: 2018-09-13.10:15:15
New experiments results are here:

At a first glance the results look promising for me. The 32 bit blind search
looses a bit in time score, but this seems to be random noise to me. We do save
a lot of memory for 64bit bjolp :).
msg7393 (view) Author: salome Date: 2018-09-12.12:52:05
We resolved all comments and started a new batch of experiments.
msg7378 (view) Author: malte Date: 2018-09-11.18:43:38
We had a look at the code. Looks great!
I left some comments on bitbucket.

In addition to the bitbucket comments, I think that "new" and "delete" should be
replaced by uses of "unique_ptr" in both PerStateInformation and PerStateArray,
unless there is a reason not to.

When comparing PerStateInformation and PerStateArray, some "clean-ups" in
PerStateArray have been carried over to PerStateInformation (e.g. using auto in
one place, using "= delete", using nullptr), but others have only been applied
to PerStateInformation (e.g. "using" instead of "typedef" and a range-based for
loop). I think it would valuable to migrate these changes over to
PerStateInformation because the two classes will be easier to maintain if they
stay more similar.

For the same reason of keeping the two files more similar, I wonder if we should
not move ArrayView to its own file, but I won't insist on this.

I see that we did not implement const look-up for PerStateArray. I understand
why (it would have required implementing a ConstArrayView?), but of course it is
a bit unfortunate to have this difference in interface between
PerStateInformation and PerStateArray. If people try to use the non-existing
method, it would be good if they could get a helpful message that tells them
what needs to be done. How about implementing the method, but making it just do

ABORT("PerStateArray::operator[] const not implemented. "
      "See source code for more information.");

And then in the source code just below the ABORT a comment like:

  This method is not implemented because it is currently not used and
  would require quite a bit of boilerplate, introducing a ConstArrayView
  class similar to ArrayView. If you need it, it should be easy to
  implement based on PerStateInformation:operator[] const.

It would be nicer to have the (run-time) ABORT be a compile-time error instead
if the method is used, but I don't know how to do that.
msg7373 (view) Author: malte Date: 2018-09-11.16:33:35
Can you add the experiments to the repository?
msg7258 (view) Author: jendrik Date: 2018-06-08.19:02:39
I made a few minor comments, but I'll leave the detailed review to Florian, the 
per-state expert :-)
msg7249 (view) Author: malte Date: 2018-06-08.16:42:08
Results look great! +10 coverage for 32 bits, +24 coverage for 64 bits, and 64
bits has finally caught up with 32 bits in terms of coverage. In terms of time
and memory scores, 64 bits also compares favourably with 32 bits. (For the
memory score that's a bit of a surprise, but we'll take it.)

How do we proceed in terms of code reviews? We may get there faster if someone
else looks at it first, and I then only do a light or no review, but there's a
risk that this will create extra work if we have contradictory feedback.
msg7244 (view) Author: salome Date: 2018-06-08.15:02:46
A first implementation is ready for this and preliminary test show decent results.

Link to pull request:

Experiments 32 bit:

Experiments 64 bit:
msg5881 (view) Author: jendrik Date: 2016-12-14.15:43:20
Split off from issue213.

Quoting Malte in msg5862:

"The drop for bjolp [between 32- and 64-bit builds] surprised me a bit,
so I had a look how it stores a landmark data, and it uses a
PerStateInformation<vector<bool>>, which is very wasteful because we
pay the vector overhead for every single state. For our state
representation, we moved from SegmentedVector to SegmentedArrayVector
for this reason, and it made a big difference. We should probably do a
similar thing here, i.e., have something like PerStateInformation
optimized for same-size arrays. (And because this is a vector<bool>, we
additionally need to pack individual bits.)"
Date User Action Args
2018-09-13 17:26:29salomesetstatus: in-progress -> resolved
messages: + msg7441
2018-09-13 11:44:31maltesetmessages: + msg7421
2018-09-13 11:14:54salomesetmessages: + msg7420
2018-09-13 10:15:15salomesetmessages: + msg7419
2018-09-12 12:52:05salomesetmessages: + msg7393
2018-09-11 18:43:39maltesetmessages: + msg7378
2018-09-11 16:33:35maltesetmessages: + msg7373
2018-06-08 19:02:39jendriksetmessages: + msg7258
2018-06-08 16:42:08maltesetmessages: + msg7249
2018-06-08 15:02:46salomesetmessages: + msg7244
2016-12-20 10:39:59manuelsetstatus: unread -> in-progress
nosy: + salome, manuel
2016-12-14 15:43:20jendrikcreate