Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Mandy Chung
The MODULES list in the `release` file is topologically sorted.
For a given module graph, the patch traverses the graph in a
stable order during the topological sort that will produce
the same result for the same module graph.

Webrev at:
http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.00/

Thanks
Mandy
Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Alan Bateman


On 05/12/2017 22:19, mandy chung wrote:
> The MODULES list in the `release` file is topologically sorted.
> For a given module graph, the patch traverses the graph in a
> stable order during the topological sort that will produce
> the same result for the same module graph.
>
> Webrev at:
> http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.00/
This looks okay to me.

-Alan
Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Andrej Golovnin
In reply to this post by Mandy Chung
Hi Mandy,

src/jdk.jlink/share/classes/jdk/tools/jlink/internal/ModuleSorter.java

 105         Deque<ResourcePoolModule> nodes = new LinkedList<>();
 106         graph.keySet().stream()
 107              .sorted(Comparator.comparing(ResourcePoolModule::name))
 108              .forEach(nodes::add);

It is suboptimal from the performance standpoint of view. Simpler and better:

List<ResourcePoolModule> nodes = new ArrayList<>(graph.keySet());
nodes.sort(Comparator.comparing(ResourcePoolModule::name));

But maybe you can solve the sorting problem just by using the TreeMap
for the graph variable in the line 51 and the TreeSet in the method
addNode(ResourcePoolModule).

A little bit unrelated to your changes:

 110         Deque<ResourcePoolModule> visited = new LinkedList<>();
 111         Deque<ResourcePoolModule> done = new LinkedList<>();

visited and done should be of type Set<ResourcePoolModule> to avoid
linear searching in the lines 114, 128, 129.

Best regards,
Andrej Golovnin

On Tue, Dec 5, 2017 at 11:19 PM, mandy chung <[hidden email]> wrote:

> The MODULES list in the `release` file is topologically sorted.
> For a given module graph, the patch traverses the graph in a
> stable order during the topological sort that will produce
> the same result for the same module graph.
>
> Webrev at:
> http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.00/
>
> Thanks
> Mandy
Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Mandy Chung
Hi Andrej,

Thanks for the suggestion.  This code does not have to be performance
sensitive but I will look at it and clean it up.

Mandy

On 12/6/17 2:08 AM, Andrej Golovnin wrote:

> Hi Mandy,
>
> src/jdk.jlink/share/classes/jdk/tools/jlink/internal/ModuleSorter.java
>
>   105         Deque<ResourcePoolModule> nodes = new LinkedList<>();
>   106         graph.keySet().stream()
>   107              .sorted(Comparator.comparing(ResourcePoolModule::name))
>   108              .forEach(nodes::add);
>
> It is suboptimal from the performance standpoint of view. Simpler and better:
>
> List<ResourcePoolModule> nodes = new ArrayList<>(graph.keySet());
> nodes.sort(Comparator.comparing(ResourcePoolModule::name));
>
> But maybe you can solve the sorting problem just by using the TreeMap
> for the graph variable in the line 51 and the TreeSet in the method
> addNode(ResourcePoolModule).
>
> A little bit unrelated to your changes:
>
>   110         Deque<ResourcePoolModule> visited = new LinkedList<>();
>   111         Deque<ResourcePoolModule> done = new LinkedList<>();
>
> visited and done should be of type Set<ResourcePoolModule> to avoid
> linear searching in the lines 114, 128, 129.
>
> Best regards,
> Andrej Golovnin
>
> On Tue, Dec 5, 2017 at 11:19 PM, mandy chung <[hidden email]> wrote:
>> The MODULES list in the `release` file is topologically sorted.
>> For a given module graph, the patch traverses the graph in a
>> stable order during the topological sort that will produce
>> the same result for the same module graph.
>>
>> Webrev at:
>> http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.00/
>>
>> Thanks
>> Mandy

Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Mandy Chung
In reply to this post by Andrej Golovnin
Updated webrev:
http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.01/

I kept the nodes as a Deque as it polls one node for traversal.   I
fixed line 110-111 to use a Set.

thanks
Mandy

Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Claes Redestad
Hi

On 2017-12-06 17:28, mandy chung wrote:
> Updated webrev:
> http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.01/

looks good, but... :-)

>
> I kept the nodes as a Deque as it polls one node for traversal.

Does it have to, though? 'nodes' is a local variable, so polling versus
iterating
doesn't matter here. So it seems:

          ResourcePoolModule node;
          while ((node = nodes.poll()) != null) {
              if (!visited.contains(node)) {
                  visit(node, visited, done);
              }
          }

... could be replaced with:

          for (ResourcePoolModule node : nodes) {
              if (!visited.contains(node)) {
                  visit(node, visited, done);
              }
          }

Together with Andrej's suggestion for simplifying creation of nodes as
an ArrayList directly this would make the code cleaner and faster.

While I agree this isn't too critical from a performance point of view,
hotspot devs building slowdebug regularly comment on how long time
jlinking the JDK images take, so we shouldn't frown too hard at
opportunities to speed things up (even though this likely doesn't matter
much on its own...)

Thanks!

/Claes
Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Mandy Chung
Okay this is a better version (traversing the graph keyset directly):

http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.02/

Mandy

Reply | Threaded
Open this post in threaded view
|

Re: Review Request JDK-8192945: Need stable sort for MODULES entry in the release file

Andrej Golovnin
Hi Mandy,

it looks good. Thanks!

@Claes when you would like to improve the performance of jlink a
little bit more, then take look at the method #entryToFileName in the
class DefaultImageBuilder lines 358-359:

        String module = "/" + entry.moduleName() + "/";
        String filename = entry.path().substring(module.length());

The value of 'module' is not used after the second line. ;-)

And you can also try to use a parallel stream in the method
#storeFiles in the same class by adding

                .parallel()

after the line 169. I have not tested it but I think it should work.

What you can also try is to increase the size of the buffer used in
Files#copy(InputStream, OutputStream) or you change the implementation
of the Files class to use the new method
InputStream#transferTo(OutputStream) and increase the size of the
buffer in InputStream. In my opinion 8kb is to small. 16kb or even
32kb would be much better.

Best regards,
Andrej Golovnin

On Wed, Dec 6, 2017 at 6:50 PM, mandy chung <[hidden email]> wrote:
> Okay this is a better version (traversing the graph keyset directly):
>
> http://cr.openjdk.java.net/~mchung/jdk10/webrevs/8192945/webrev.02/
>
> Mandy
>