You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@iotdb.apache.org by GitBox <gi...@apache.org> on 2022/08/14 12:47:45 UTC
[GitHub] [iotdb] ZhanGHanG9991 opened a new pull request, #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
ZhanGHanG9991 opened a new pull request, #6986:
URL: https://github.com/apache/iotdb/pull/6986
## Description
Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
<!--
In each section, please describe design decisions made, including:
- Choice of algorithms
- Behavioral aspects. What configuration values are acceptable? How are corner cases and error
conditions handled, such as when there are insufficient resources?
- Class organization and design (how the logic is split between classes, inheritance, composition,
design patterns)
- Method organization and design (how the logic is split between methods, parameters and return types)
- Naming (class, method, API, configuration, HTTP endpoint, names of emitted metrics)
-->
<!-- It's good to describe an alternative design (or mention an alternative name) for every design
(or naming) decision point and compare the alternatives with the designs that you've implemented
(or the names you've chosen) to highlight the advantages of the chosen designs and names. -->
<!-- If there was a discussion of the design of the feature implemented in this PR elsewhere
(e. g. a "Proposal" issue, any other issue, or a thread in the development mailing list),
link to that discussion from this PR description and explain what have changed in your final design
compared to your original proposal or the consensus version in the end of the discussion.
If something hasn't changed since the original discussion, you can omit a detailed discussion of
those aspects of the design here, perhaps apart from brief mentioning for the sake of readability
of this PR description. -->
<!-- Some of the aspects mentioned above may be omitted for simple and small changes. -->
<hr>
This PR has:
- [x] been self-reviewed.
- [ ] concurrent read
- [ ] concurrent write
- [ ] concurrent read and write
- [ ] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods.
- [ ] added or updated version, __license__, or notice information
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious
for an unfamiliar reader.
- [ ] added unit tests or modified existing tests to cover new code paths, ensuring the threshold
for code coverage.
- [ ] added integration tests.
- [ ] been tested in a test IoTDB cluster.
<!-- Check the items by putting "x" in the brackets for the done things. Not all of these items
apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items
from the checklist above are strictly necessary, but it would be very helpful if you at least
self-review the PR. -->
<hr>
##### Key changed/added classes (or packages if there are too many classes) in this PR
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] JackieTien97 merged pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
Posted by GitBox <gi...@apache.org>.
JackieTien97 merged PR #6986:
URL: https://github.com/apache/iotdb/pull/6986
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] lancelly commented on a diff in pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
Posted by GitBox <gi...@apache.org>.
lancelly commented on code in PR #6986:
URL: https://github.com/apache/iotdb/pull/6986#discussion_r946428152
##########
server/src/main/java/org/apache/iotdb/db/mpp/transformation/datastructure/Cache.java:
##########
@@ -64,33 +69,37 @@ protected Cache(int capacity) {
cachedNodes[i] = new Node();
}
+ valueToNode = new HashMap<>();
+
cacheCapacity = capacity;
cacheSize = 0;
}
protected boolean removeFirstOccurrence(int value) {
- for (Node node = head.succeeding; node != tail; node = node.succeeding) {
- if (node.value == value) {
- cachedNodes[--cacheSize] = node.remove();
- return true;
- }
+ if (valueToNode.containsKey(value)) {
+ cachedNodes[--cacheSize] = valueToNode.get(value).remove();
+ return true;
}
return false;
}
protected int removeLast() {
Node last = tail.previous.remove();
cachedNodes[--cacheSize] = last;
+ valueToNode.remove(last.value);
return last.value;
}
protected void addFirst(int value) {
- cachedNodes[cacheSize++].set(head, value, head.succeeding);
+ cachedNodes[cacheSize].set(head, value, head.succeeding);
+ valueToNode.put(value, cachedNodes[cacheSize]);
Review Comment:
Does this work well when encounters duplicate keys?
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] lancelly commented on a diff in pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
Posted by GitBox <gi...@apache.org>.
lancelly commented on code in PR #6986:
URL: https://github.com/apache/iotdb/pull/6986#discussion_r956529852
##########
server/src/main/java/org/apache/iotdb/db/mpp/transformation/datastructure/Cache.java:
##########
@@ -19,6 +19,9 @@
package org.apache.iotdb.db.mpp.transformation.datastructure;
+import java.util.HashMap;
+import java.util.Map;
+
/** <b>Note: It's not thread safe.</b> */
public abstract class Cache {
Review Comment:
This class could be removed.
##########
server/src/main/java/org/apache/iotdb/db/mpp/transformation/datastructure/OldCache.java:
##########
@@ -0,0 +1,96 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iotdb.db.mpp.transformation.datastructure;
+
+/** <b>Note: It's not thread safe.</b> */
+public abstract class OldCache {
Review Comment:
This class could be removed.
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] ZhanGHanG9991 commented on pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
Posted by GitBox <gi...@apache.org>.
ZhanGHanG9991 commented on PR #6986:
URL: https://github.com/apache/iotdb/pull/6986#issuecomment-1217438096
### Performance Statistics
- NewLRUCache is implemented by LinkedHashMap.
- LRUCache is implemented by original doubly linked list and HashMap.
- OldLRUCacheis implemented by original doubly linked list.
| Method | Cache Size / Data Size | NewLRUCache Time | LRUCache Time | OldLRUCache Time |
| :----: | :--------------------: | :--------------: | :-----------: | :--------------: |
| Random | 0.07 | 0.412s | 0.819s | 1.440s |
| Random | 0.1 | 0.389s | 0.765s | 1.449s |
| Random | 0.2 | 0.356s | 0.721s | 1.361s |
| Random | 0.3 | 0.365s | 0.601s | 1.303s |
| Random | 0.4 | 0.361s | 0.622s | 1.268s |
| Random | 0.5 | 0.339s | 0.490s | 1.154s |
| Random | 0.6 | 0.318s | 0.422s | 1.170s |
| Random | 0.7 | 0.191s | 0.320s | 1.115s |
| Random | 0.8 | 0.193s | 0.323s | 1.142s |
| Random | 0.9 | 0.194s | 0.319s | 0.924s |
| Method | Cache Size / Data Size | NewLRUCache Time | LRUCache Time | OldLRUCache Time |
| :----: | :--------------------: | :--------------: | :-----------: | :--------------: |
| Scan | 0.07 | 0.338s | 0.979s | 1.384s |
| Scan | 0.1 | 0.330s | 0.950s | 1.383s |
| Scan | 0.2 | 0.325s | 0.822s | 1.708s |
| Scan | 0.3 | 0.307s | 0.685s | 1.720s |
| Scan | 0.4 | 0.308s | 0.547s | 1.713s |
| Scan | 0.5 | 0.285s | 0.445s | 1.724s |
| Scan | 0.6 | 0.292s | 0.443s | 1.713s |
| Scan | 0.7 | 0.289s | 0.441s | 1.714s |
| Scan | 0.8 | 0.288s | 0.442s | 1.721s |
| Scan | 0.9 | 0.293s | 0.442s | 1.722s |
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] lancelly commented on a diff in pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop
Posted by GitBox <gi...@apache.org>.
lancelly commented on code in PR #6986:
URL: https://github.com/apache/iotdb/pull/6986#discussion_r956529832
##########
server/src/main/java/org/apache/iotdb/db/mpp/transformation/datastructure/NewCache.java:
##########
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.iotdb.db.mpp.transformation.datastructure;
+
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+public abstract class NewCache extends LinkedHashMap<Integer, Integer> {
Review Comment:
Rename to Cache.
--
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.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org