You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "yytInHfut (via GitHub)" <gi...@apache.org> on 2023/10/08 19:16:57 UTC
[I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
yytInHfut opened a new issue, #395:
URL: https://github.com/apache/datasketches-cpp/issues/395
hello,
I just benchmarked the tuple sketch within this lib, and found the "update" on array_of_doubles_intersection have poor performance when the size(distinct entries) of aod scale up.
While the Java version keeps high performance. Maybe, there is a bug? @AlexanderSaydakov
For example
```c++
double DUM[] = {0};
int common_size = 50000;
datasketches::update_array_of_doubles_sketch::builder builder(1);
datasketches::update_array_of_doubles_sketch sk1 = builder.set_lg_k(14).build();
datasketches::update_array_of_doubles_sketch sk2 = builder.set_lg_k(14).build();
for (int key = 0; key < 2 * common_size; key++) {
sk1.update(key, DUM);
}
for (int key = common_size; key < 3 * common_size; key++) {
sk2.update(key, DUM);
}
datasketches::compact_array_of_doubles_sketch sketch1 = sk1.compact();
datasketches::compact_array_of_doubles_sketch sketch2 = sk2.compact();
datasketches::array_of_doubles_intersection<datasketches::array_of_doubles_union_policy> inter;
auto startTime = std::chrono::high_resolution_clock::now();
inter.update(sketch1);
inter.update(sketch2);
auto interResult = inter.get_result();
auto endTime = std::chrono::high_resolution_clock::now();
auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime);
// Output the union sketch estimates
std::cout << "Intersection took " << elapsedTime.count() << " milliseconds to run." << std::endl;
std::cout << "Intersection unique count estimate: " << interResult.get_estimate() << std::endl;
std::cout << "Intersection unique count lower bound (95% confidence): " << interResult.get_lower_bound(2) << std::endl;
std::cout << "Intersection unique count upper bound (95% confidence): " << interResult.get_upper_bound(2) << std::endl;
```
Outputs:
```
common_size: 50000
Intersection took 13065 milliseconds to run.
Intersection unique count estimate: 49500.2
Intersection unique count lower bound (95% confidence): 48801.7
Intersection unique count upper bound (95% confidence): 50208.7
```
```
common_size: 500000
Intersection took 6394 milliseconds to run.
Intersection unique count estimate: 501315
Intersection unique count lower bound (95% confidence): 492070
Intersection unique count upper bound (95% confidence): 510733
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1765065015
Sorry for the delay. I think I reproduced the problem. Not sure of the cause yet.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "yytInHfut (via GitHub)" <gi...@apache.org>.
yytInHfut commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1754218186
Thanks for your reply.
The Java code and results:
```java
final static int commonSizes = 50000;
final static double[] DUM = new double[] {0};
public static void main(String[] args) {
for (int j = 0; j < 10; j++) {
ArrayOfDoublesUpdatableSketch sketchA = new ArrayOfDoublesUpdatableSketchBuilder().setNominalEntries(1<<14).build();
for (int i = 0; i < 2 * commonSizes; i++) {
sketchA.update(i , DUM);
}
ArrayOfDoublesUpdatableSketch sketchB = new ArrayOfDoublesUpdatableSketchBuilder().setNominalEntries(1<<14).build();
for (int i = commonSizes; i < 3 * commonSizes; i++) {
sketchB.update(i, DUM);
}
System.out.println(sketchA);
ArrayOfDoublesCompactSketch skA = sketchA.compact();
ArrayOfDoublesCompactSketch skB = sketchB.compact();
ArrayOfDoublesSetOperationBuilder builder = new ArrayOfDoublesSetOperationBuilder();
ArrayOfDoublesIntersection intersection = builder.buildIntersection();
long start = System.currentTimeMillis();
intersection.intersect(skA, (a, b) -> a);
intersection.intersect(skB, (a, b) -> a);
ArrayOfDoublesCompactSketch result = intersection.getResult();
System.out.println("iteration: " + j);
System.out.println("common_size: " + commonSizes);
System.out.println("run time: " + (System.currentTimeMillis() - start) + "ms");
System.out.println("Intersection unique count estimate: " + result.getEstimate());
System.out.println("Intersection unique count estimate lower bound 95% confidence: " + result.getLowerBound(2));
System.out.println("Intersection unique count estimate upper bound 95% confidence: " + result.getUpperBound(2));
System.out.println();
}
}
```
Outputs:
```
iteration: 9
common_size: 50000
run time: 2ms
Intersection unique count estimate: 49500.199335479825
Intersection unique count estimate lower bound 95% confidence: 48801.65021039344
Intersection unique count estimate upper bound 95% confidence: 50208.70802304575
```
```
iteration: 9
common_size: 500000
run time: 1ms
Intersection unique count estimate: 501314.8477448015
Intersection unique count estimate lower bound 95% confidence: 492069.85049213597
Intersection unique count estimate upper bound 95% confidence: 510733.10167792573
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1771801197
I have just tried calling System.gc() before the measurement. I see 175 ms on the first iteration and stabilizing around 21 ms 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.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1771792107
I am afraid that this is not a fair comparison. You are not taking into account Java garbage collection, but in C++ most of it is included except a few final objects that might be destroyed after the measurement is done. Iteration 9 shows 2ms, but iteration 1 shows 16ms, which is even slower than C++.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "yytInHfut (via GitHub)" <gi...@apache.org>.
yytInHfut commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1767587290
Java aod intersection benchmark result:
```
Benchmark (commonSizes) Mode Cnt Score Error Units
BenchMarkAod.benchAodIntersect 500 avgt 5 7463.752 ± 801.980 ns/op
BenchMarkAod.benchAodIntersect 5000 avgt 5 111925.572 ± 2776.117 ns/op
BenchMarkAod.benchAodIntersect 50000 avgt 5 457008.096 ± 162147.561 ns/op
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "yytInHfut (via GitHub)" <gi...@apache.org>.
yytInHfut commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1763407340
hi
I want to know if I am using the lib in the wrong way or if there is really a problem.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "yytInHfut (via GitHub)" <gi...@apache.org>.
yytInHfut closed issue #395: Tuple: Update array_of_doubles_intersection have poor performance
URL: https://github.com/apache/datasketches-cpp/issues/395
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "AlexanderSaydakov (via GitHub)" <gi...@apache.org>.
AlexanderSaydakov commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1753462155
What are the numbers for Java?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [I] Tuple: Update array_of_doubles_intersection have poor performance [datasketches-cpp]
Posted by "yytInHfut (via GitHub)" <gi...@apache.org>.
yytInHfut commented on issue #395:
URL: https://github.com/apache/datasketches-cpp/issues/395#issuecomment-1767554394
Really thanks for your work and reply.
I tried your commit. Yes, it worked.
But I wonder why the intersection performance is not as good as Java.
Another strange point is the common_size 50000 took more time than 500000, 5000000.
```
common_size: 50000
Intersection took 11 milliseconds to run.
Intersection unique count estimate: 49500.2
Intersection unique count lower bound (95% confidence): 48801.7
Intersection unique count upper bound (95% confidence): 50208.7
```
```
common_size: 500000
Intersection took 8 milliseconds to run.
Intersection unique count estimate: 501315
Intersection unique count lower bound (95% confidence): 492070
Intersection unique count upper bound (95% confidence): 510733
```
```
common_size: 5000000
Intersection took 7 milliseconds to run.
Intersection unique count estimate: 4.98187e+06
Intersection unique count lower bound (95% confidence): 4.87864e+06
Intersection unique count upper bound (95% confidence): 5.08727e+06
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org