[jira] [Commented] (GIRAPH-314) Implement better message grouping to improve performance in SimpleTriangleClosingVertex
[ https://issues.apache.org/jira/browse/GIRAPH-314?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13486437#comment-13486437 ] Eli Reisman commented on GIRAPH-314: Not too worried about getting this in, its still an experiment and its one I'm not provisioned to stress test at the moment. When things in the message passing plumbing settle down, I will come back to this. The results I got were intriguing in practice, but as someone like Sebastian would tell you, this does not represent a solution to the message growth problems with triangle closing. If this is a JIRA issue holding up the new release, we can mark this won't fix. Otherwise, I'll come back to it when the messaging code ripens or I have a proper cluster to abuse. Schemes are afoot for both... ;) Implement better message grouping to improve performance in SimpleTriangleClosingVertex --- Key: GIRAPH-314 URL: https://issues.apache.org/jira/browse/GIRAPH-314 Project: Giraph Issue Type: Improvement Components: examples Affects Versions: 0.2.0 Reporter: Eli Reisman Assignee: Eli Reisman Priority: Trivial Fix For: 0.2.0 Attachments: GIRAPH-314-1.patch, GIRAPH-314-2.patch, GIRAPH-314-3.patch, GIRAPH-314-4.patch After running SimpleTriangleClosingVertex at scale I'm thinking the sendMessageToAllEdges() is pretty in the code, but its not a good idea in practice since each vertex V sends degree(V)^2 messages right in the first superset in this algorithm. Could do something with a combiner etc. but just grouping messages by hand at the application level by using IntArrayListWritable again does the trick fine. Probably should have just done it this way before, but sendMessageToAllEdges() looked so nice. Sigh. Changed unit tests to reflect this new approach, passes mvn verify and cluster, etc. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-314) Implement better message grouping to improve performance in SimpleTriangleClosingVertex
[ https://issues.apache.org/jira/browse/GIRAPH-314?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13454725#comment-13454725 ] Maja Kabiljo commented on GIRAPH-314: - Sorry that I keep asking about this, but here is the thing I'm trying to get to with your problem size discussion: is above described combiner together with limiting number of open requests (but still everything in-core) a good alternative to this solution, and if not why not? Amortizing says convert messages to these maps every once in a while - that's what combiner could do. And amortizing says wait for part of messages to be processed before sending/receiving new ones - that's what limiting number of open requests does. Implement better message grouping to improve performance in SimpleTriangleClosingVertex --- Key: GIRAPH-314 URL: https://issues.apache.org/jira/browse/GIRAPH-314 Project: Giraph Issue Type: Improvement Components: examples Affects Versions: 0.2.0 Reporter: Eli Reisman Assignee: Eli Reisman Priority: Trivial Fix For: 0.2.0 Attachments: GIRAPH-314-1.patch, GIRAPH-314-2.patch, GIRAPH-314-3.patch, GIRAPH-314-4.patch After running SimpleTriangleClosingVertex at scale I'm thinking the sendMessageToAllEdges() is pretty in the code, but its not a good idea in practice since each vertex V sends degree(V)^2 messages right in the first superset in this algorithm. Could do something with a combiner etc. but just grouping messages by hand at the application level by using IntArrayListWritable again does the trick fine. Probably should have just done it this way before, but sendMessageToAllEdges() looked so nice. Sigh. Changed unit tests to reflect this new approach, passes mvn verify and cluster, etc. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-314) Implement better message grouping to improve performance in SimpleTriangleClosingVertex
[ https://issues.apache.org/jira/browse/GIRAPH-314?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13455093#comment-13455093 ] Eli Reisman commented on GIRAPH-314: No problem, I welcome the input. The combiner is not needed at the beginning or is just an extra step once at the sending side, because we just combined the messages using IntArrayListWritable instead of many IntWritables right from the get go. From the receiver side, combiners don't help us much because we still have incredible amounts of extra messages coming in over Netty all the time as long as the are serialized and de-serialized organized around Partition - vertexid - ListM and thats what GIRAPH-322 addresses. As for the message limiting, as long as the sender does not keep iterating on compute() and we don't overwhelm the sender that way, its a great idea. But once we serialize-deserialize to disk or anywhere else, we lose the single reference to each message and we get back individual objects, which then have to be put into a sender-side combiner or other extra plumbing, or just sent out duplicated on Netty. And we're talking about degree(V)^2 messages for all V in G(V) so its a lot to churn through in one superstep. The amortizing is fast and by avoiding the disk we leave the possibility for GIRAPH-322 to manage the message growth without serializing-deserializing and ending up with a bunch of instances to send over the wire again or random access on the disk. So I'm not conviced 314 + 322 are a good alternative, but they seem worth exploring at this point. If it turns out the only way to make large jobs on an application like 314 run to completion is to focus on spill to disk entirely, I will certainly embrace that route. Implement better message grouping to improve performance in SimpleTriangleClosingVertex --- Key: GIRAPH-314 URL: https://issues.apache.org/jira/browse/GIRAPH-314 Project: Giraph Issue Type: Improvement Components: examples Affects Versions: 0.2.0 Reporter: Eli Reisman Assignee: Eli Reisman Priority: Trivial Fix For: 0.2.0 Attachments: GIRAPH-314-1.patch, GIRAPH-314-2.patch, GIRAPH-314-3.patch, GIRAPH-314-4.patch After running SimpleTriangleClosingVertex at scale I'm thinking the sendMessageToAllEdges() is pretty in the code, but its not a good idea in practice since each vertex V sends degree(V)^2 messages right in the first superset in this algorithm. Could do something with a combiner etc. but just grouping messages by hand at the application level by using IntArrayListWritable again does the trick fine. Probably should have just done it this way before, but sendMessageToAllEdges() looked so nice. Sigh. Changed unit tests to reflect this new approach, passes mvn verify and cluster, etc. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (GIRAPH-314) Implement better message grouping to improve performance in SimpleTriangleClosingVertex
[ https://issues.apache.org/jira/browse/GIRAPH-314?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanelfocusedCommentId=13450883#comment-13450883 ] Eli Reisman commented on GIRAPH-314: I'd love for us to move this to GIRAPH-322 and get your input now that the code is up and you can see what the idea was, I am instrumenting it now so I can see where I messed up the wiring, but the basic idea is there. I didn't implement the combiner option yet in the solution I put up. I would be interested in trying some more as I am sure you're right that with better tuning (or more expert tuning) disk spill should be a part of a final solution. I was surprised it didn't work too, it looks like it should handle exactly this situation. And again, with better tuning perhaps it will. But I was running real data, and a lot of it. Everyone here has noted the benchmarks are great for A/B'ing Giraph as it improves and measuring progress in a sane way, but not great for comparing with conditions out in the wild. I'm hoping GIRAPH-26 will help close this gap, but for us the benchmarks have been poor predictors of real performance in our target use-cases. As for my solution so far, the idea is to reduce the # of partitions to one per worker with -Dhash.userPartitionCount and then store messages so that only a single object is in memory at any given time (with one reference per partition destination), and they simply accumulate destination vertices and flush regularly. The only real messages that go out is 1 per partition that requires a copy of that message (depending on which vertices need it) which will differ per-message. Again, I tried to make the patch simple and changeable so we can tune this or improve the idea and try things to see what works best. The problem I had so far with combiners is they just aggregate messages for one vertex rather than destinations for one message. In the solution so far I found it easier to just sort of set this stuff up by hand to happen since we are in a special case where we know something we can use about the properties of a message sent with sendMessageToAllEdges() and can avoid some of the object creations and checks along the way. As you said, the place for a combiner in this scenario if anywhere seems to be on the receiving end. Now that the game plan patch is up, I'll be very interest in ideas and observations. If this gets any traction, we could then set up a disk spill strategy for these types of messages that does not re-duplicate them on load (since the message stores are all currently set up for Giraph's existing Partition - Vertex - ListM paradigm.) Alternately, the whole exercise might be a waste of time ;) but I have it on good authority this is a route worth pursuing, so we'll see where it leads. Implement better message grouping to improve performance in SimpleTriangleClosingVertex --- Key: GIRAPH-314 URL: https://issues.apache.org/jira/browse/GIRAPH-314 Project: Giraph Issue Type: Improvement Components: examples Affects Versions: 0.2.0 Reporter: Eli Reisman Assignee: Eli Reisman Priority: Trivial Fix For: 0.2.0 Attachments: GIRAPH-314-1.patch, GIRAPH-314-2.patch, GIRAPH-314-3.patch, GIRAPH-314-4.patch After running SimpleTriangleClosingVertex at scale I'm thinking the sendMessageToAllEdges() is pretty in the code, but its not a good idea in practice since each vertex V sends degree(V)^2 messages right in the first superset in this algorithm. Could do something with a combiner etc. but just grouping messages by hand at the application level by using IntArrayListWritable again does the trick fine. Probably should have just done it this way before, but sendMessageToAllEdges() looked so nice. Sigh. Changed unit tests to reflect this new approach, passes mvn verify and cluster, etc. -- This message is automatically generated by JIRA. If you think it was sent incorrectly, please contact your JIRA administrators For more information on JIRA, see: http://www.atlassian.com/software/jira