darcs

Patch 1891 add Darcs.Util.Graph.components with pro... (and 5 more)

Title add Darcs.Util.Graph.components with pro... (and 5 more)
Superseder Nosy List bf
Related Issues
Status accepted Assigned To bf
Milestone

Created on 2019-08-26.09:43:31 by bf, last changed 2019-08-31.14:14:21 by ganesh.

Files
File name Status Uploaded Type Edit Remove
add-darcs_util_graph_components-with-properties-and-tests.dpatch bf, 2019-08-26.09:43:30 application/x-darcs-patch
avoid-unsafe-indexing-in-darcs_util_graph_components.dpatch bf, 2019-08-31.00:17:19 application/x-darcs-patch
patch-preview.txt bf, 2019-08-26.09:43:30 text/x-darcs-patch
patch-preview.txt bf, 2019-08-31.00:17:19 text/x-darcs-patch
unnamed bf, 2019-08-26.09:43:30 text/plain
unnamed bf, 2019-08-31.00:17:19 text/plain
See mailing list archives for discussion on individual patches.
Messages
msg21200 (view) Author: bf Date: 2019-08-26.09:43:30
... and yet one less V3INTEGRATION item. Yay!

6 patches for repository http://darcs.net/screened:

patch ec98ed9308dd1d4e41c1c4814049e59b16e61892
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 14:34:34 CEST 2019
  * add Darcs.Util.Graph.components with properties and tests

patch 70e5a05cbd3a101582a23b22b33680a7602d68a5
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 18:26:06 CEST 2019
  * simplify and improve Darcs.Util.Graph.components
  
  It wasn't incorrect (according to the spec) but it did not always return
  vertices ordered and also did a bit too much work.

patch 10f31d86c1275da3a54e50814bb69a6c7baa9843
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 15:31:04 CEST 2019
  * replace quickcheck with leancheck for testing Graph properties
  
  Calculating graph properties scales very badly because the specifications
  aren't optimised (naturally). Exhaustive testing with leancheck is a lot
  more effective here because we avoid testing with (too) large graphs.
  Unfortunately test-framework is a bit limited in that it doesn't allow to
  scale the number of tests, just to set them to a fixed value. We opt to
  set it to 0x8000 which covers all graphs up to size 6.

patch 179677ce4e328e0fb6bc3b9db977da28b40499b2
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 18:23:21 CEST 2019
  * move functions to generate graphs from harness to library

patch 9012663a6a2fb6b4c46db0994697a4901e8151d5
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 14:32:25 CEST 2019
  * remove Darcs.Util.Graph.bk and some minor refactors

patch c4630e4db47190ca95b346a81017fa62a704a390
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sun Aug 25 23:19:20 CEST 2019
  * use Darcs.Util.Graph.components for RepoPatchV3
  
  This required a few refactors and the introduction of a new data type for
  components. In particular, the ltmis algorithm needs to be adapted to
  working with just a subset of the vertices of a graph.
Attachments
msg21288 (view) Author: ganesh Date: 2019-08-30.22:08:55
>   * replace quickcheck with leancheck for testing Graph properties
>
>   Calculating graph properties scales very badly because the
>   specifications aren't optimised (naturally). Exhaustive testing with
>   leancheck is a lot more effective here because we avoid testing with
>   (too) large graphs. Unfortunately test-framework is a bit limited in
>   that it doesn't allow to scale the number of tests, just to set them
>   to a fixed value. We opt to set it to 0x8000 which covers all graphs
>   up to size 6.

It'd be helpful to put the comments about why 0x8000 and why leancheck
in the code.

BTW we might consider switching from test-framework to tasty, I think
test-framework is in maintenance-only mode nowadays. From what I'm aware
tasty is its natural successor.

>   * remove Darcs.Util.Graph.bk and some minor refactors

OK

>   * add Darcs.Util.Graph.components with properties and tests
BTW I had to apply the patches in this order (which is not the order
they were sent) to avoid build breaks.

> components :: Graph -> [VertexSet]

Given the unsafe indexing inside this, I presume we could get a segfault
if it is passed an invalid Graph. I'm not sure whether to be concerned
about that or not. I'd be inclined to play it safe unless you're sure
this really matters performance-wise. Just replacing the unsafeRead
should be good enough as it also guards the unsafeWrite.

Rest is fine.

>   * simplify and improve Darcs.Util.Graph.components

OK (the unsafeRead comment from above still applies)

>   * move functions to generate graphs from harness to library

OK

>   * use Darcs.Util.Graph.components for RepoPatchV3
>   
>   This required a few refactors and the introduction of a new data type for
>   components. In particular, the ltmis algorithm needs to be adapted to
>   working with just a subset of the vertices of a graph.

Is this because previously we constructed the graphs after calculating
the components, so each component had a self-contained graph with
contiguous numbering?

I didn't read the code in detail but I'll assume the tests are good enough.
msg21290 (view) Author: bf Date: 2019-08-31.00:17:19
Following up on review.

3 patches for repository http://darcs.net/screened:

patch 3d22624bcb10d0da6b444c416960c8e6d4b28dfc
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug 31 01:03:30 CEST 2019
  * avoid unsafe indexing in Darcs.Util.Graph.components
  
  I guess it's not important to press the last bit of performance out of this
  piece of code. Anyway, before we use unsafe indexing we should at least run
  some sort of benchmark to convince us of the necessity.

patch 64eb05e6edb946230d9eb8dabb79b1db8c12e186
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug 31 02:18:49 CEST 2019
  * explain why we use leancheck for testing graph algorithms

patch 769c632cff2fa7200664b30f1b6c3ff37d3f5e42
Author: Ben Franksen <ben.franksen@online.de>
Date:   Sat Aug 31 02:20:09 CEST 2019
  * explain the number of tests used for testing graph algorithms
Attachments
msg21292 (view) Author: bf Date: 2019-08-31.01:21:09
Oops, forgot to send.

>>   Calculating graph properties scales very badly because the
>>   specifications aren't optimised (naturally). Exhaustive testing with
>>   leancheck is a lot more effective here because we avoid testing with
>>   (too) large graphs. Unfortunately test-framework is a bit limited in
>>   that it doesn't allow to scale the number of tests, just to set them
>>   to a fixed value. We opt to set it to 0x8000 which covers all graphs
>>   up to size 6.
> 
> It'd be helpful to put the comments about why 0x8000 and why leancheck
> in the code.

Will do.

> BTW we might consider switching from test-framework to tasty, I think
> test-framework is in maintenance-only mode nowadays. From what I'm aware
> tasty is its natural successor.

I agree that this would be the right move, but not keen on doing it
myself. If you feel like it, go ahead.

>>   * add Darcs.Util.Graph.components with properties and tests
> BTW I had to apply the patches in this order (which is not the order
> they were sent) to avoid build breaks.

Yet another missing explicit dependency. Can we automatically add them
using your new 'darcs test' features perhaps? Something like "try to
build project with all re-orderings of unpublished patches, inserting
dependencies whenever a commute breaks a build?

>> components :: Graph -> [VertexSet]
> 
> Given the unsafe indexing inside this, I presume we could get a segfault
> if it is passed an invalid Graph. I'm not sure whether to be concerned
> about that or not. I'd be inclined to play it safe unless you're sure
> this really matters performance-wise. Just replacing the unsafeRead
> should be good enough as it also guards the unsafeWrite.

I agree that using the safe read and write operations should be fast
enough in practice. I am not sure why I didn't use them in the first
place, this is just unwarranted premature optimization. Will fix.

>>   * use Darcs.Util.Graph.components for RepoPatchV3
>>   
>>   This required a few refactors and the introduction of a new data type for
>>   components. In particular, the ltmis algorithm needs to be adapted to
>>   working with just a subset of the vertices of a graph.
> 
> Is this because previously we constructed the graphs after calculating
> the components, so each component had a self-contained graph with
> contiguous numbering?

Yes, exactly. The mapping from the list of Nodes to the Graph and back
is usually a bottleneck and therefore shouldn't be done more than once.
I found it unfortunate that this seemed to reduce compositionality,
which is why I added the Component data type as a new concept.

> I didn't read the code in detail but I'll assume the tests are good enough.

Exhaustive testing with a complete specification really gave me a warm
fuzzy feeling! This was fun to write and it actually worked the first
time I ran it. Though at first I did have a few bugs in the properties
that needed fixing before the tests succeeded :-)

BTW, I didn't want to go overboard with the new leancheck thing, but
there are a few closely related packages with interesting
functionalities, like discovering laws through testing and (to come to
the point) detecting redundancy among laws and IIRC also detecting
whether a set of laws fully specifies a function. Some of that may come
in handy in the future.
msg21300 (view) Author: ganesh Date: 2019-08-31.10:15:27
> Yet another missing explicit dependency. Can we automatically add them
> using your new 'darcs test' features perhaps? Something like "try to
> build project with all re-orderings of unpublished patches, inserting
> dependencies whenever a commute breaks a build?

It sounds plausible as a feature for 'darcs test', but I don't think
there's any connection with the features I was adding which were really
all about handling "untestable" states.
History
Date User Action Args
2019-08-26 09:43:31bfcreate
2019-08-26 20:54:10bfsetstatus: needs-screening -> needs-review
2019-08-30 22:08:55ganeshsetmessages: + msg21288
2019-08-30 22:09:06ganeshsetstatus: needs-review -> followup-requested
assignedto: bf
2019-08-31 00:17:20bfsetfiles: + patch-preview.txt, avoid-unsafe-indexing-in-darcs_util_graph_components.dpatch, unnamed
messages: + msg21290
2019-08-31 01:21:10bfsetmessages: + msg21292
2019-08-31 08:45:41ganeshsetstatus: followup-requested -> review-in-progress
2019-08-31 10:13:43ganeshsetstatus: review-in-progress -> accepted-pending-tests
2019-08-31 10:15:27ganeshsetmessages: + msg21300
2019-08-31 14:14:21ganeshsetstatus: accepted-pending-tests -> accepted