qpid-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "ASF GitHub Bot (Jira)" <j...@apache.org>
Subject [jira] [Commented] (PROTON-2178) Implement efficient search of encoded Symbol on ReadableBuffer
Date Fri, 27 Mar 2020 16:24:00 GMT

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

ASF GitHub Bot commented on PROTON-2178:
----------------------------------------

gemmellr commented on pull request #36: PROTON-2178 Implement efficient search of encoded
Symbol on ReadableBuffer
URL: https://github.com/apache/qpid-proton-j/pull/36#discussion_r399379661
 
 

 ##########
 File path: proton-j/src/main/java/org/apache/qpid/proton/amqp/Symbol.java
 ##########
 @@ -60,6 +66,82 @@ public CharSequence subSequence(int beginIndex, int endIndex)
         return _underlying.subSequence(beginIndex, endIndex);
     }
 
+    /**
+     * https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm jump table
+     */
+    private static int[] createJumpTable(byte[] needle) {
+        final int[] jumpTable = new int[needle.length + 1];
+        int j = 0;
+        for (int i = 1; i < needle.length; i++) {
+            while (j > 0 && needle[j] != needle[i]) {
+                j = jumpTable[j];
+            }
+            if (needle[j] == needle[i]) {
+                j++;
+            }
+            jumpTable[i + 1] = j;
+        }
+        for (int i = 1; i < jumpTable.length; i++) {
+            if (jumpTable[i] != 0) {
+                return jumpTable;
+            }
+        }
+        // optimization over the original algorithm: it would save from accessing any jump
table
+        return null;
+    }
+
+    private int[] racyGerOrCreateJumpTable() {
+        int[] jumpTable = this._jumpTable;
+        if (jumpTable == NOT_INITIALIZED_JUMP_TABLE) {
+            jumpTable = createJumpTable(this._underlyingBytes);
+            _jumpTable = jumpTable;
+        }
+        return jumpTable;
+    }
+
+    /**
+     * Returns the index on buffer of the first encoded occurrence of this {@code symbol}
within the specified range.<br>
+     * If none is found, then {@code -1} is returned.
+     *
+     * @param buffer the buffer where to search in
+     * @return the index of the first occurrence of this symbol or {@code -1} if it won't
occur.
+     * <p>
+     * @throws IllegalArgumentException if any of the indexes of the specified range is negative
+     */
+    public int searchFirst(ReadableBuffer buffer, int from, int to)
+    {
+        Objects.requireNonNull(buffer, "buffer cannot be null");
+        if (from < 0 || to < 0)
+        {
+            throw new IllegalArgumentException("range indexes cannot be negative!");
+        }
+        int j = 0;
+        final int[] jumpTable = racyGerOrCreateJumpTable();
+        final byte[] needle = _underlyingBytes;
+        final long length = to - from;
+        final ReadableBuffer haystack = buffer;
+        final int needleLength = needle.length;
+        for (int i = 0; i < length; i++)
 
 Review comment:
   Would initialising i to 'from' rather than 0 simplify things? (Plus other adjustments accordingly,
e.g rename i to index, to rather than length)
 
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


> Implement efficient search of encoded Symbol on ReadableBuffer
> --------------------------------------------------------------
>
>                 Key: PROTON-2178
>                 URL: https://issues.apache.org/jira/browse/PROTON-2178
>             Project: Qpid Proton
>          Issue Type: New Feature
>          Components: proton-j
>    Affects Versions: proton-c-0.30.0
>            Reporter: Francesco Nigro
>            Priority: Minor
>              Labels: perf
>




--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@qpid.apache.org
For additional commands, e-mail: dev-help@qpid.apache.org


Mime
View raw message