Mailing-List: contact issues-help@flink.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@flink.apache.org
Date: Fri, 21 Aug 2015 11:53:45 +0000 (UTC)
From: "Gabor Gevay (JIRA)" <jira@apache.org>
To: issues@flink.apache.org
Message-ID: <JIRA.12857260.1440002407000.129271.1440158025656@Atlassian.JIRA>
In-Reply-To: <JIRA.12857260.1440002407000@Atlassian.JIRA>
References: <JIRA.12857260.1440002407000@Atlassian.JIRA>
 <JIRA.12857260.1440002407727@arcas>
Subject: [jira] [Commented] (FLINK-2548) In a VertexCentricIteration, the
 run time of one iteration should be proportional to the size of the workset
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ https://issues.apache.org/jira/browse/FLINK-2548?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14706579#comment-14706579 ] 

Gabor Gevay commented on FLINK-2548:
------------------------------------

I changed the title of the issue to refer to the goal instead of the above proposed solution approach, because I'm not sure anymore that this is the best approach to achieve this.

My problem with the join + reduceGroup approach is that there are cases where it is a little slower (few ten percent) then the coGroup, for example when the edges data set doesn't fit into memory, and probably also when the workset size is close to all the vertices.

Another approach would be to extend the coGroup operation to have an option which makes it call the UDF only for the matching keys (inner join), and the optimizer would consider using a hashtable instead of sorting if this option is set. But I am not sure how big work would be to implement this.

> In a VertexCentricIteration, the run time of one iteration should be proportional to the size of the workset
> ------------------------------------------------------------------------------------------------------------
>
>                 Key: FLINK-2548
>                 URL: https://issues.apache.org/jira/browse/FLINK-2548
>             Project: Flink
>          Issue Type: Improvement
>          Components: Gelly
>    Affects Versions: 0.9, 0.10
>            Reporter: Gabor Gevay
>            Assignee: Gabor Gevay
>
> Currently, the performance of vertex centric iteration is suboptimal in those iterations where the workset is small, because the complexity of one iteration contains the number of edges and vertices of the graph because of coGroups:
> VertexCentricIteration.buildMessagingFunction does a coGroup between the edges and the workset, to get the neighbors to the messaging UDF. This is problematic from a performance point of view, because the coGroup UDF gets called on all the edge groups, including those that are not getting any messages.
> An analogous problem is present in VertexCentricIteration.createResultSimpleVertex at the creation of the updates: a coGroup happens between the messages and the solution set, which has the number of vertices of the graph included in its complexity.
> Both of these coGroups could be avoided by doing a join instead (with the same keys that the coGroup uses), and then a groupBy. The complexity of these operations would be dominated by the size of the workset, as opposed to the number of edges or vertices of the graph. The joins should have the edges and the solution set at the build side to achieve this complexity. (They will not be rebuilt at every iteration.)
> I made some experiments with this, and the initial results seem promising. On some workloads, this achieves a 2 times speedup, because later iterations often have quite small worksets, and these get a huge speedup from this.


--
This message was sent by Atlassian JIRA
(v6.3.4#6332)