Return-Path: X-Original-To: apmail-flink-issues-archive@minotaur.apache.org Delivered-To: apmail-flink-issues-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 2E9E817EE9 for ; Tue, 1 Sep 2015 08:20:47 +0000 (UTC) Received: (qmail 7635 invoked by uid 500); 1 Sep 2015 08:20:47 -0000 Delivered-To: apmail-flink-issues-archive@flink.apache.org Received: (qmail 7440 invoked by uid 500); 1 Sep 2015 08:20:47 -0000 Mailing-List: contact issues-help@flink.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@flink.apache.org Delivered-To: mailing list issues@flink.apache.org Received: (qmail 7332 invoked by uid 99); 1 Sep 2015 08:20:46 -0000 Received: from arcas.apache.org (HELO arcas.apache.org) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 01 Sep 2015 08:20:46 +0000 Date: Tue, 1 Sep 2015 08:20:46 +0000 (UTC) From: "ASF GitHub Bot (JIRA)" To: issues@flink.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Commented] (FLINK-2590) DataSetUtils.zipWithUniqueID creates duplicate IDs MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/FLINK-2590?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14724961#comment-14724961 ] ASF GitHub Bot commented on FLINK-2590: --------------------------------------- Github user s1ck commented on the pull request: https://github.com/apache/flink/pull/1075#issuecomment-136633442 @tillrohrmann of course you are right, I thought wrong about it. it's committed > DataSetUtils.zipWithUniqueID creates duplicate IDs > -------------------------------------------------- > > Key: FLINK-2590 > URL: https://issues.apache.org/jira/browse/FLINK-2590 > Project: Flink > Issue Type: Bug > Components: Java API, Scala API > Affects Versions: 0.10, master > Reporter: Martin Junghanns > Assignee: Martin Junghanns > Priority: Minor > > The function creates IDs using the following code: > {code:java} > shifter = log2(numberOfParallelSubtasks) > id = counter << shifter + taskId; > {code} > As the binary function + is executed before the bitshift <<, this results in cases where different tasks create the same ID. It essentially calculates > {code} > counter*2^(shifter+taskId) > {code} > which is 0 for counter = 0 and all values of shifter and taskID. > Consider the following example. > numberOfParallelSubtaks = 8 > shifter = log2(8) = 4 (maybe rename the function?) > produces: > {code} > start: 1, shifter: 4 taskId: 4 label: 256 > start: 2, shifter: 4 taskId: 3 label: 256 > start: 4, shifter: 4 taskId: 2 label: 256 > {code} > I would suggest the following: > {code} > counter*2^(shifter)+taskId > {code} > which in code is equivalent to > {code} > shifter = log2(numberOfParallelSubtasks); > id = (counter << shifter) + taskId; > {code} > and for our example produces: > {code} > start: 1, shifter: 4 taskId: 4 label: 20 > start: 2, shifter: 4 taskId: 3 label: 35 > start: 4, shifter: 4 taskId: 2 label: 66 > {code} > So we move the counter to the left and add the task id. As there is space for 2^shifter numbers, this prevents collisions. -- This message was sent by Atlassian JIRA (v6.3.4#6332)