You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hbase.apache.org by "Jason Rutherglen (JIRA)" <ji...@apache.org> on 2011/06/17 21:31:47 UTC
[jira] [Created] (HBASE-4002) Int array based skip list
Int array based skip list
-------------------------
Key: HBASE-4002
URL: https://issues.apache.org/jira/browse/HBASE-4002
Project: HBase
Issue Type: Improvement
Reporter: Jason Rutherglen
Priority: Minor
We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: (was: HBASE-3954.patch)
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: HBASE-4002.patch
Here's an updated patch where in IntSkipList, the 2 value linked list isn't used anymore to keep array symmetry.
I need to abstract out the linked lists so that they implement the same interface.
When adding a value, start wasn't being used correctly in some cases, it now always is.
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: HBASE-4002.patch
Here's the skip list.
Need to:
* Add reusable 'starts' int array
* Runs tests randomly, and perhaps improve them somehow
* Execute a benchmark vs. ConcurrentSkipListMap for single threaded writes and multithreaded reads
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: HBASE-4002.patch
HBASE-3954.patch
This is an implementation of a sorted linked list in an atomic integer array. Currently it assumes a single threaded writer, and multiple threads reading.
Concurrent reading threads needs to be tested.
Each element consists of 2 ints. The first int is the value, the second is the pointer to the next element.
Each add locates the position between which the new element should be linked.
An append to the end of the array is performed, then the linked list pointers are changed.
Dynamic resizing needs to be implemented.
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: (was: HBASE-4002.patch)
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-4002) Int array based skip list
Posted by "Lars Hofhansl (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13443625#comment-13443625 ]
Lars Hofhansl commented on HBASE-4002:
--------------------------------------
Is there anything to do here for HBase? Jason, are you still around?
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
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] [Updated] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jason Rutherglen updated HBASE-4002:
------------------------------------
Attachment: HBASE-4002.patch
HBASE-4002.patch
Added dynamic resizing of the internal int array.
Added the ability to subclass and add a custom comparator, eg, for use when comparing byte arrays.
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-4002) Int array based skip list
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13051280#comment-13051280 ]
Jason Rutherglen commented on HBASE-4002:
-----------------------------------------
Once this seems to work, then a 3 int version of this linked list will be created. The third int is the down skip level pointer.
The next step is the logic that assembles the skip lists effectively, which will be based what's in ConcurrentSkipListMap.
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-4002) Int array based skip list
Posted by "Ted Yu (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-4002?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13054957#comment-13054957 ]
Ted Yu commented on HBASE-4002:
-------------------------------
In IntLinkedList3.copyOf():
{code}
+ int size = source.length();
+ for (int x = 0; x < size; x++) {
+ newone.set(x, source.get(x));
+ }
{code}
Should we check size against newSize and use the smaller one ?
I guess the method names below can be made more intuitive ?
{code}
+ public static void setNex(int pos, int next, AtomicIntegerArray linkedList) {
+ linkedList.set( (pos * CONST) + 1, next);
+ }
+
+ public static void setDow(int pos, int down, AtomicIntegerArray linkedList) {
+ linkedList.set( (pos * CONST) + 2, down);
+ }
{code}
> Int array based skip list
> -------------------------
>
> Key: HBASE-4002
> URL: https://issues.apache.org/jira/browse/HBASE-4002
> Project: HBase
> Issue Type: Improvement
> Reporter: Jason Rutherglen
> Priority: Minor
> Attachments: HBASE-4002.patch, HBASE-4002.patch, HBASE-4002.patch
>
>
> We can implement an AtomicIntegerArray based skip list, where the int values point to locations in a byte block structure. This can be useful for testing against ConcurrentSkipListMap. It can also be used in Lucene for the realtime terms dictionary.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira