You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2020/04/02 08:04:34 UTC
[GitHub] [lucene-solr] CaoManhDat opened a new pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
CaoManhDat opened a new pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402201394
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntIntArrayBasedMap.java
##########
@@ -0,0 +1,81 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.IntConsumer;
+
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntIntArrayBasedMap implements IntIntMap {
+
+ private int size;
+ private int[] keyValues;
+ private int emptyValue;
+
+ public IntIntArrayBasedMap(int initialSize, int emptyValue) {
+ this.size = initialSize;
+ this.keyValues = new int[initialSize];
+ this.emptyValue = emptyValue;
+ if (emptyValue != 0) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ }
+
+ @Override
+ public void set(int key, int value) {
+ if (key >= size) {
+ keyValues = ArrayUtil.grow(keyValues);
Review comment:
Here keyValues is enlarged (based on its current capacity), but are we sure it is enlarged enough to hold "key"?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405355937
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/DynamicMap.java
##########
@@ -0,0 +1,35 @@
+/*
+ * 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.solr.util.numeric;
+
+import com.carrotsearch.hppc.HashContainers;
+
+public interface DynamicMap {
+ static boolean useArrayBased(int expectedMaxSize) {
+ // for small size, prefer using array based
+ return expectedMaxSize < (1 << 12);
+ }
+
+ static int threshold(int expectedMaxSize) {
+ return expectedMaxSize >>> 6;
+ }
+
+ static int mapExpectedElements(int expectedMaxSize) {
+ return (int) (threshold(expectedMaxSize) / HashContainers.DEFAULT_LOAD_FACTOR);
Review comment:
why it is safer?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on a change in pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405061864
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/DynamicMap.java
##########
@@ -17,13 +17,19 @@
package org.apache.solr.util.numeric;
-import java.util.function.Consumer;
-import java.util.function.IntConsumer;
+import com.carrotsearch.hppc.HashContainers;
-public interface IntIntMap {
- void set(int key, int value);
- int get(int key);
- void forEachValue(IntConsumer consumer);
- void remove(int key);
- int size();
+public interface DynamicMap {
+ static boolean useArrayBased(int expectedMaxSize) {
+ // for small data set, prefer using array based
+ return expectedMaxSize < (1 << 12);
Review comment:
if assertions are enabled, then perhaps return false so as to have tests test the DynamicMap. I've seen @yonik use this technique in data structure sizing and thought it was clever.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402691881
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
That is what I thought in the first place and HPPC primitive map did gave a very good result in our performance test on large collection (number of unique values in the collapsing field is 1.2million), around 5x better in qps.
But when I write a simple single-thread benchmark test (I can add it here in this PR so you can try to tune it).
- Number of docs are 300k
- 95% percent of queries are sparse ones so we only doing collapsing on 1% of docs.
Array approach actually do better than map (around 1.5x better). The reason for that is
- We don't now how much size we gonna need for the map, so we pay lot of cost on resizing the map.
- Map needs 2 array for storing key and value seperately, plus with above point it leads to more memory usage.
I just don't want to do a commit that can potentially slow down users. Although switching to HPPC primitive map is much easier and makes thing simple for me.
Any idea on this @dsmiley @shalinmangar @joel-bernstein
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use. I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo. So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so we kinda safe here, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use. I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo. So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements / 0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so we kinda safe here, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on a change in pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405061981
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/DynamicMap.java
##########
@@ -17,13 +17,19 @@
package org.apache.solr.util.numeric;
-import java.util.function.Consumer;
-import java.util.function.IntConsumer;
+import com.carrotsearch.hppc.HashContainers;
-public interface IntIntMap {
- void set(int key, int value);
- int get(int key);
- void forEachValue(IntConsumer consumer);
- void remove(int key);
- int size();
+public interface DynamicMap {
Review comment:
Needs docs!
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610712750
> Why are sizes before and after rehash added?
You analysis is actually correct, thanks!
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402691881
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
That is what I thought in the first place and HPPC primitive map did gave a very good result in our performance test on large collection (number of unique values in the collapsing field is 1.2million), around 5x better in qps.
But when I write a simple single-thread benchmark test (I can add it here in this PR so you can try to tune it).
- Number of docs are 300k
- 95% percent of queries are sparse ones so we only doing collapsing on 1% of docs.
Array approach actually do better than map (around 1.5x better). The reason for that is
- We don't now how much size we gonna need for the map, so we pay lot of cost on resizing the map.
- Map needs 2 array for storing key and value seperately, plus with above point it leads to more memory usage.
I just don't want to do a commit that can potentially slow down users. Although switching to HPPC primitive map is much easier and makes thing simple for me.
Any idea on this @dsmiley @shalinmangar @joel-bernstein
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-611288608
@dsmiley Done!
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-611020236
Yes I missed the power of 2. So I'll just let you double check this works without wasteful map resize.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405403028
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/FloatConsumer.java
##########
@@ -0,0 +1,23 @@
+/*
+ * 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.solr.util.numeric;
+
+@FunctionalInterface
+public interface FloatConsumer {
Review comment:
Javadoc: similar to java.util.function.IntConsumer
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use (why they want to use DynamicMaps insteads of hppc maps or java maps). I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo and `initialCapacity` is not equals to `expectedElements`.
So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
I realized that `threshold < mapExpectedElements <= resizeAt`.
So we actually can compute maxExpectedElements = threshold + 2, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use (why they want to use DynamicMaps insteads of hppc maps or java maps). I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo and `initialCapacity` is not equals to `expectedElements`.
So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
I realized that `threshold < mapExpectedElements <= resizeAt`.
So we actually can compute maxExpectedElements = threshold - 2, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on a change in pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405098834
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
Review comment:
On a related note, do we even want to bother resizing this array vs size it appropriately up-front?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405478717
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
+ growBuffer(key + 1);
+ }
+ keyValues[key] = value;
+ } else {
+ this.hashMap.put(key, value);
+ this.maxSize = Math.max(key, maxSize);
+ if (this.hashMap.size() > threshold) {
Review comment:
Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
Let's take an example with expectedKeyMax = 500K.
this.threshold = threshold(expectedKeyMax) = 500000/64 = 7812
IntFloatHashMap initial capacity = mapExpectedElements(expectedKeyMax) = (int) (threshold(expectedKeyMax) / 0.75f) = (int) (7812 / 0.75f) = 10416
IntFloatHashMap internal threshold = ceil(initial capacity * 0.75) = ceil(10416 * 0.75) = 7812
Internally the HPPC map enlarges during a put() when its size == 7812 *before* incrementing the size.
Here the condition to upgrade to an array triggers when the map size *after* the put is > 7812, so at 7813.
So I think the map first enlarges and rehashes just before we upgrade to an array, which would be wasteful.
Also, the map internal threshold is ceil(initial capacity * 0.75), but it could be without ceil() for other implementations. To be safe wrt the float rounding, I suggested to add +1 in DynamicMap. mapExpectedElements(int), but it is probably better to be safe here.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use (why they want to use DynamicMaps insteads of hppc maps or java maps). I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo and `initialCapacity` is not equals to `expectedElements`.
So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so we kinda safe here, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402825437
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
If some preliminary perf tests show that sometime the array version is clearly faster, then I agree we should invest in an automated switch logic. But in this case the interfaces presented in this PR do not fit this switch logic: we should be able to change the underlying implementation of the map seamlessly. This is more work.
I would like to understand better the simple benchmark test you did, because the reason for the speed/memory difference is still not obvious to me.
> 95% percent of queries are sparse ones so we only doing collapsing on 1% of docs.
Does that mean that only 1% of the 300K docs are put in the map?
So on the map implementation side we have an internal capacity of 2^12 (4K) or 2^13 (8K) for 2 arrays.
On the array implementation side we have 1 array of 300K.
For the memory the map is more efficient. For the speed, it will depend on the actual load factor and the map implementation.
> So start with a hash based map with a substantial initial capacity (not 4!), then upgrade to an array based map impl
Or maybe the reverse? This depends on the map load factor.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-611274493
Thanks a lot for your hard work @bruno-roustant
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402198934
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntIntArrayBasedMap.java
##########
@@ -0,0 +1,81 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.IntConsumer;
+
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntIntArrayBasedMap implements IntIntMap {
+
+ private int size;
Review comment:
Should be named "capacity" rather than "size".
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on a change in pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405252783
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -2258,29 +2215,20 @@ public void collapse(int collapseKey, int contextDoc, int globalDoc) throws IOEx
final int idx;
if((idx = cmap.indexOf(collapseKey)) >= 0) {
int pointer = cmap.indexGet(idx);
- if(comp.test(currentVal, testValues[pointer])) {
- testValues[pointer]= currentVal;
- docs[pointer] = globalDoc;
+ if(comp.test(currentVal, testValues.get(pointer))) {
+ testValues.set(pointer, currentVal);
+ docs.set(pointer, globalDoc);
if(needsScores) {
- scores[pointer] = scorer.score();
+ scores.set(pointer, scorer.score());
}
}
} else {
++index;
cmap.put(collapseKey, index);
- if(index == testValues.length) {
- testValues = ArrayUtil.grow(testValues);
Review comment:
Thanks for pointing that out; I had thought the numerical range was pre-determined but I see in this scenario (numeric DocValues), it is not. Keep the resizing in there then; as long as the other cases we size correctly up-front.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610481938
> so in total we pay 2^22 + 2^23 bytes
Why are sizes before and after rehash added?
I take an example of a max number of elements of 1 M known ahead.
The array size will be exactly 1M, so memory = 1M * element size B.
For a load of 1.5%, the map memory = 2^16 * element size B.
(nextPowerOf2(15000/0.75)=2^15)
So I get a ratio of array mem / map mem = 15.25
For a load of 15%, the map memory = 2^19 * element size.
(nextPowerOf2(150000/0.75)=2^18)
So I get a ratio of array mem / map mem = 1.9
For a load of 20%, the map memory = 2^20 * element size.
(nextPowerOf2(200000/0.75)=2^19)
So I get a ratio of array mem / map mem = 0.95
Above 20% load, the array memory is less than the map memory.
So if we want to focus on the memory benefit, we can set a threshold at 20% load. If we want the performance we can set the threshold lower.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610286455
@dsmiley @bruno-roustant Can you take a second look at this?
I created a simple benchmark for between maps implementation (https://github.com/apache/lucene-solr/pull/1395/commits/a1be3dd08f506990b81e7aae08aa6a4ec8ec869f#diff-2cd03d050427fa8bea6ced064c32ad42).
Basically it just a linear set and get from 0 to n (portion of maxSize), and here is the result. With x-axis is `n_maxSize`, and y-axis is time taken.
We can see that `dynamicMap` is much better than the worst most of time and not too worse than the best.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r404980774
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
Review comment:
Actually I missed here something risky: what if a large key is provided? We have no protection here yet. Nothing prevents the user to put a key 500M. In this case we should not grow the array too large just for one key.
Maybe we should have a strong limit on the map capacity in the constructor.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r403416444
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
Ok then I will add the benchmark class here and may be delete it in subsequence commits.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405086508
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/DynamicMap.java
##########
@@ -17,13 +17,19 @@
package org.apache.solr.util.numeric;
-import java.util.function.Consumer;
-import java.util.function.IntConsumer;
+import com.carrotsearch.hppc.HashContainers;
-public interface IntIntMap {
- void set(int key, int value);
- int get(int key);
- void forEachValue(IntConsumer consumer);
- void remove(int key);
- int size();
+public interface DynamicMap {
+ static boolean useArrayBased(int expectedMaxSize) {
+ // for small data set, prefer using array based
+ return expectedMaxSize < (1 << 12);
Review comment:
+1
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405356167
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
+ growBuffer(key + 1);
+ }
+ keyValues[key] = value;
+ } else {
+ this.hashMap.put(key, value);
+ this.maxSize = Math.max(key, maxSize);
+ if (this.hashMap.size() > threshold) {
Review comment:
why it is safer?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use. I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo. So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (768/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so we kinda safe here, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-611307658
@dsmiley DynamicMap doesn't have any methods that subclass needs to implement. `DynamicMap` is just an interface that can be used to group related classes in a logical way.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402687019
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntIntArrayBasedMap.java
##########
@@ -0,0 +1,81 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.IntConsumer;
+
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntIntArrayBasedMap implements IntIntMap {
+
+ private int size;
+ private int[] keyValues;
+ private int emptyValue;
+
+ public IntIntArrayBasedMap(int initialSize, int emptyValue) {
+ this.size = initialSize;
+ this.keyValues = new int[initialSize];
+ this.emptyValue = emptyValue;
+ if (emptyValue != 0) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ }
+
+ @Override
+ public void set(int key, int value) {
+ if (key >= size) {
+ keyValues = ArrayUtil.grow(keyValues);
+ if (emptyValue != 0) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ size = keyValues.length;
+ }
+ keyValues[key] = value;
+ }
+
+ @Override
+ public int get(int key) {
+ if (key >= size) {
+ return emptyValue;
+ }
+ return keyValues[key];
+ }
+
+ @Override
+ public void forEachValue(IntConsumer consumer) {
+ for (int val: keyValues) {
+ if (val != emptyValue) {
+ consumer.accept(val);
+ }
+ }
+ }
+
+ @Override
+ public void remove(int key) {
+ if (key < size) keyValues[key] = emptyValue;
+ }
+
+ @Override
+ public int size() {
+ return keyValues.length;
Review comment:
Thanks! This kinda like a debug method and I will delete it.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat closed pull request #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat closed pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r404785908
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/DynamicMap.java
##########
@@ -0,0 +1,35 @@
+/*
+ * 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.solr.util.numeric;
+
+import com.carrotsearch.hppc.HashContainers;
+
+public interface DynamicMap {
+ static boolean useArrayBased(int expectedMaxSize) {
+ // for small size, prefer using array based
+ return expectedMaxSize < (1 << 12);
+ }
+
+ static int threshold(int expectedMaxSize) {
+ return expectedMaxSize >>> 6;
+ }
+
+ static int mapExpectedElements(int expectedMaxSize) {
+ return (int) (threshold(expectedMaxSize) / HashContainers.DEFAULT_LOAD_FACTOR);
Review comment:
Safer to add +1
(int) (threshold(expectedMaxSize) / HashContainers.DEFAULT_LOAD_FACTOR) + 1
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405478717
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
+ growBuffer(key + 1);
+ }
+ keyValues[key] = value;
+ } else {
+ this.hashMap.put(key, value);
+ this.maxSize = Math.max(key, maxSize);
+ if (this.hashMap.size() > threshold) {
Review comment:
Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
Let's take an example with expectedKeyMax = 500K.
this.threshold = threshold(expectedKeyMax) = 500000/64 = 7812
IntFloatHashMap initial capacity = mapExpectedElements(expectedKeyMax) = (int) (threshold(expectedKeyMax) / 0.75f) = (int) (7812 / 0.75f) = 10416
IntFloatHashMap internal threshold = ceil(initial capacity * 0.75) = ceil(10416 * 0.75) = 7812
Internally the HPPC map enlarges during a put() when its size == 7812 *before* incrementing the size.
Here the condition to upgrade to an array triggers when the map size *after* the put is > 7812, so at 7813.
So I think the map first enlarges and rehashes just before we upgrade to an array, which would be wasteful.
Also, the map internal threshold is ceil(initial capacity * 0.75), but it could be without ceil() for other implementations. To be safe wrt the float rounding, I suggested to add +1 in DynamicMap. mapExpectedElements(int).
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402825437
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
If some preliminary perf tests show that sometime the array version is clearly faster, then I agree we should invest in an automated switch logic. But in this case the interfaces presented in this PR do not fit this switch logic: we should be able to change the underlying implementation of the map seamlessly. This is more work.
I would like to understand better the simple benchmark test you did, because the reason for the speed/memory difference is still not obvious to me.
> 95% percent of queries are sparse ones so we only doing collapsing on 1% of docs.
Does that mean that only 1% of the 300K docs are put in the map?
So on the map implementation side we have an internal capacity of 2^12 (4K) or 2^13 (8K) for 2 arrays.
On the array implementation side we have 1 array of 300K.
For the memory the map is more efficient. For the speed, it will depend on the actual load factor and the map implementation.
> So start with a hash based map with a substantial initial capacity (not 4!), then upgrade to an array based map impl
Or maybe the reverse? This depends on the map load factor.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-611276129
Dat can you move out of the numeric package please
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use. I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo and `initialCapacity` is not equals to `expectedElements`.
So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so we kinda safe here, right?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat merged pull request #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat merged pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402687112
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntIntArrayBasedMap.java
##########
@@ -0,0 +1,81 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.IntConsumer;
+
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntIntArrayBasedMap implements IntIntMap {
+
+ private int size;
+ private int[] keyValues;
+ private int emptyValue;
+
+ public IntIntArrayBasedMap(int initialSize, int emptyValue) {
+ this.size = initialSize;
+ this.keyValues = new int[initialSize];
+ this.emptyValue = emptyValue;
+ if (emptyValue != 0) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ }
+
+ @Override
+ public void set(int key, int value) {
+ if (key >= size) {
+ keyValues = ArrayUtil.grow(keyValues);
Review comment:
oh, right! :+1
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r404786529
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
+ growBuffer(key + 1);
+ }
+ keyValues[key] = value;
+ } else {
+ this.hashMap.put(key, value);
+ this.maxSize = Math.max(key, maxSize);
+ if (this.hashMap.size() > threshold) {
Review comment:
Safer to test >=
if (this.hashMap.size() >= threshold) {
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610481938
> so in total we pay 2^22 + 2^23 bytes
Why are sizes before and after rehash added?
I take an example of a max number of elements of 1 M known ahead.
The array size will be exactly 1M, so memory = 1M * element size B.
For a load of 1.5%, the map memory = 2^16 * element size B.
(nextPowerOf2(15000/0.75)=2^15)
So I get a ratio of array mem / map mem = 15.25
For a load of 15%, the map memory = 2^19 * element size.
(nextPowerOf2(150000/0.75)=2^18)
So I get a ratio of array mem / map mem = 1.9
For a load of 20%, the map memory = 2^20 * element size.
(nextPowerOf2(200000/0.75)=2^19)
So I get a ratio of array mem / map mem = 0.95
Above 20% load, the array memory is less than the map memory.
So if we want to focus on the memory benefit, we can set a threshold at 20% load. If we want the performance we can set the threshold lower.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610517184
Also, we have to explain very clearly in the javadoc that this map is designed for range-limited keys. The design to switch to an array does not work as well for keys in the whole Integer range. There should be a strong limit param in the constructor to enforce that.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat opened a new pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat opened a new pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405411173
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
Review comment:
The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk. Mainly because the class is named Map, and a Map generally can take any key value.
Could we create a second constructor with a third param, something like "hardLimitKeyMax" which would be checked here otherwise throw an IllegalArgumentException? It could have a default limit of 10x expectedKeyMax in the first constructor for example. And it could be increased if someone knows what she is doing.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] dsmiley commented on a change in pull request #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
dsmiley commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402711624
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
I suggest we take inspiration from two similar places in Lucene/Solr: `org.apache.lucene.util.DocIdSetBuilder` and `org.apache.solr.search.DocSetBuilder` which are doing essentially the same thing. Basically, start with a memory efficient data structure, and then once we reach a threshold, switch on the fly to a larger but more efficient structure.
So start with a hash based map with a substantial initial capacity (not 4!), then upgrade to an array based map impl _instead of resizing the map_ if we exceed that capacity. This might be done with a map impl that delegates to the real impl (hppc) with switch/resize logic.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405217227
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -2258,29 +2215,20 @@ public void collapse(int collapseKey, int contextDoc, int globalDoc) throws IOEx
final int idx;
if((idx = cmap.indexOf(collapseKey)) >= 0) {
int pointer = cmap.indexGet(idx);
- if(comp.test(currentVal, testValues[pointer])) {
- testValues[pointer]= currentVal;
- docs[pointer] = globalDoc;
+ if(comp.test(currentVal, testValues.get(pointer))) {
+ testValues.set(pointer, currentVal);
+ docs.set(pointer, globalDoc);
if(needsScores) {
- scores[pointer] = scorer.score();
+ scores.set(pointer, scorer.score());
}
}
} else {
++index;
cmap.put(collapseKey, index);
- if(index == testValues.length) {
- testValues = ArrayUtil.grow(testValues);
Review comment:
@dsmiley @bruno-roustant If we do not allow resizing automatically (which I would like to do), then how can we deal with this case?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r404980774
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.solr.util.numeric.DynamicMap.mapExpectedElements;
+import static org.apache.solr.util.numeric.DynamicMap.threshold;
+import static org.apache.solr.util.numeric.DynamicMap.useArrayBased;
+
+public class IntFloatDynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ public IntFloatDynamicMap(int expectedMaxSize, float emptyValue) {
+ this.threshold = threshold(expectedMaxSize);
+ this.maxSize = expectedMaxSize;
+ this.emptyValue = emptyValue;
+ if (useArrayBased(expectedMaxSize)) {
+ upgradeToArray();
+ } else {
+ this.hashMap = new IntFloatHashMap(mapExpectedElements(expectedMaxSize));
+ }
+ }
+
+ private void upgradeToArray() {
+ keyValues = new float[maxSize];
+ if (emptyValue != 0.0f) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ if (hashMap != null) {
+ hashMap.forEach((IntFloatProcedure) (key, value) -> keyValues[key] = value);
+ hashMap = null;
+ }
+ }
+
+ private void growBuffer(int minSize) {
+ assert keyValues != null;
+ int size = keyValues.length;
+ keyValues = ArrayUtil.grow(keyValues, minSize);
+ if (emptyValue != 0.0f) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ }
+
+
+ public void set(int key, float value) {
+ if (keyValues != null) {
+ if (key >= keyValues.length) {
Review comment:
Actually I missed here something risky: what if a large value key is provided? We have no protection here yet. Nothing prevents the user to put a key 500M. In this case we should not grow the array too large just for one key.
Maybe we should have a strong limit on the map capacity in the constructor.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405219705
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -2258,29 +2215,20 @@ public void collapse(int collapseKey, int contextDoc, int globalDoc) throws IOEx
final int idx;
if((idx = cmap.indexOf(collapseKey)) >= 0) {
int pointer = cmap.indexGet(idx);
- if(comp.test(currentVal, testValues[pointer])) {
- testValues[pointer]= currentVal;
- docs[pointer] = globalDoc;
+ if(comp.test(currentVal, testValues.get(pointer))) {
+ testValues.set(pointer, currentVal);
+ docs.set(pointer, globalDoc);
if(needsScores) {
- scores[pointer] = scorer.score();
+ scores.set(pointer, scorer.score());
}
}
} else {
++index;
cmap.put(collapseKey, index);
- if(index == testValues.length) {
- testValues = ArrayUtil.grow(testValues);
Review comment:
or we revert this change and handle it later?
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610426625
Thanks @bruno-roustant.
One clarification here, let's says that we pay `n` bytes (let's assume is 1 byte) to store n elements. If we specify `n` as expected elements for hashMap, the total memory we pay is
```
arraySize = nextPowerOf2(n / loadFactor)
memory = arraySize * 2
```
But that is not enough to store `n` elements, since the hashMap will resize when number of elements are greater than `arraySize * loadFactor`.
For example if n = 2^20 (1 million), loadFactor = 0.75
```
arraySize = 2^21
memory = 2^22 bytes
```
Resizing will happen at 2^21 * 0.75 = 1.5 mil
```
arraySize = 2^22
memory = 2^23 bytes
```
so in total we pay 2^22 + 2^23 bytes = 12.5 mil bytes.
Therefore the amount of memory we pay for storing n elements with hashMap is 12.5 times comparing to array. So we have a simple table here
| Load | Array / HashMap mem used |
| ------------- | ------------- |
| 1.5% | 5.3 |
| 3% | 2.67 |
| 5% | 1.6 |
| 8% | 1.0 |
| 15% | 0.53 |
Do not forget that rehashing can be slow depending on hashing and keys. So I kinda feel the current setup is good and it will help to covers most of cases. We of course can introduce a parameter that user can tune to trade-off some memory vs performance (only matter when they do collapsing on 1.5% -> 5% of their total unique values). But we can do that in another issue.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402200092
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntIntArrayBasedMap.java
##########
@@ -0,0 +1,81 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.function.IntConsumer;
+
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntIntArrayBasedMap implements IntIntMap {
+
+ private int size;
+ private int[] keyValues;
+ private int emptyValue;
+
+ public IntIntArrayBasedMap(int initialSize, int emptyValue) {
+ this.size = initialSize;
+ this.keyValues = new int[initialSize];
+ this.emptyValue = emptyValue;
+ if (emptyValue != 0) {
+ Arrays.fill(keyValues, emptyValue);
+ }
+ }
+
+ @Override
+ public void set(int key, int value) {
+ if (key >= size) {
+ keyValues = ArrayUtil.grow(keyValues);
+ if (emptyValue != 0) {
+ for (int i = size; i < keyValues.length; i++) {
+ keyValues[i] = emptyValue;
+ }
+ }
+ size = keyValues.length;
+ }
+ keyValues[key] = value;
+ }
+
+ @Override
+ public int get(int key) {
+ if (key >= size) {
+ return emptyValue;
+ }
+ return keyValues[key];
+ }
+
+ @Override
+ public void forEachValue(IntConsumer consumer) {
+ for (int val: keyValues) {
+ if (val != emptyValue) {
+ consumer.accept(val);
+ }
+ }
+ }
+
+ @Override
+ public void remove(int key) {
+ if (key < size) keyValues[key] = emptyValue;
+ }
+
+ @Override
+ public int size() {
+ return keyValues.length;
Review comment:
keyValues.length is a capacity while size() semantics is more a size: the current number of entries in the map. We should return a counter instead.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r402207235
##########
File path: solr/core/src/java/org/apache/solr/search/CollapsingQParserPlugin.java
##########
@@ -524,6 +533,7 @@ public int docID() {
public OrdScoreCollector(int maxDoc,
int segments,
+ PrimitiveMapFactory mapFactory,
Review comment:
I agree that we should use primitive map instead of array if we don't load enough arrays. The speed of the map put/get is sufficiently fast that I suppose it should not be visible in the overall perf of this CollapsingQParser.
But do we need to have a new factory for primitive map to switch between hash map and array? I think we could need this if we often had both cases (high load and low load of the array) AND if we had a way to switch automatically. But I suppose we don't know in advance (so we don't switch auto), and that most often the load is low.
So I suggest that we don't add the complexity of these new classes (the new util.numeric package) and we just use HPPC primitive map directly.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] bruno-roustant commented on a change in pull request
#1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and
float[] with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
bruno-roustant commented on a change in pull request #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#discussion_r405406935
##########
File path: solr/core/src/java/org/apache/solr/util/numeric/IntFloatDynamicMap.java
##########
@@ -0,0 +1,115 @@
+/*
+ * 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.solr.util.numeric;
+
+import java.util.Arrays;
+
+import com.carrotsearch.hppc.IntFloatHashMap;
+import com.carrotsearch.hppc.cursors.FloatCursor;
+import com.carrotsearch.hppc.procedures.IntFloatProcedure;
+import org.apache.lucene.util.ArrayUtil;
+
+public class IntFloatDynamicMap implements DynamicMap {
+ private int maxSize;
+ private IntFloatHashMap hashMap;
+ private float[] keyValues;
+ private float emptyValue;
+ private int threshold;
+
+ /**
+ * Create map with expected max value of key.
+ * Although the map will automatically do resizing to be able to hold key >= {@code expectedKeyMax}.
+ * But putting key much larger than {@code expectedKeyMax} is discourage since it can leads to use LOT OF memory.
Review comment:
We can be explicit and say: more than key x 4B, so for a max key 100M it may allocate more than 400 MB.
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat edited a comment on issue #1395:
SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[]
with size equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat edited a comment on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610985910
> The javadoc in the constructor is good, but I'm concerned that this util class may be used elsewhere without clearly reading/understanding the risk
I'm not very concern about this point much. If we gonna put this class in guava or some places like that I think it is worth to spend more time to documents or make the api right. But these classes will get used in Solr and when they use `DynamicMaps` they must have a clear idea of what they gonna use (why they want to use DynamicMaps insteads of hppc maps or java maps). I just want to avoid introduce more logic to these classes since one change needs to propagate and maintain in others.
> Did you test and debug when the DynamicMap upgrades from a map to an array internally? I mean in debug mode step by step here. I think the map first enlarges and rehashes just before the upgrade to an array.
It seems that your calculation missed the part that arraySize must be powerOfTwo and `initialCapacity` is not equals to `expectedElements`.
So I will go from backward with
`arraySize=1024` -> `mapExpectedElements=768 (arraySize = expectedElements/0.75)` -> `threshold = 768 * 0.75 = 576`
-> `resizeAt=768 (arraySize * loadFactor)`
so basically `threshold < mapExpectedElements <= resizeAt`.
We actually can compute maxExpectedElements = (int) threshold / 0.95.
( min value of threshold is 64 since we skipping using map when maxSize < 2^12 )
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene-solr] CaoManhDat commented on issue #1395: SOLR-14365:
CollapsingQParser - Avoiding always allocate int[] and float[] with size
equals to number of unique values (WIP)
Posted by GitBox <gi...@apache.org>.
CaoManhDat commented on issue #1395: SOLR-14365: CollapsingQParser - Avoiding always allocate int[] and float[] with size equals to number of unique values (WIP)
URL: https://github.com/apache/lucene-solr/pull/1395#issuecomment-610712750
| Why are sizes before and after rehash added?
You analysis is actually correct, thanks!
----------------------------------------------------------------
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
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org