| <!DOCTYPE html> |
| <!-- Start _layouts/doc_page.html--> |
| <html lang="en"> |
| |
| <head> |
| <!-- Start _include/site_head.html --> |
| <meta charset="UTF-8" /> |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| <meta name="description" content=""> |
| <meta name="author" content="datasketches"> |
| |
| <title>DataSketches | </title> |
| |
| <link rel="shortcut icon" href="/img/favicon.png"> |
| |
| <!-- original source: https://maxcdn.bootstrapcdn.com/font-awesome/4.1.0/css/font-awesome.min.css --> |
| <link rel="stylesheet" href="/css/font-awesome.min.css"> |
| <!-- original source: https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css --> |
| <link rel="stylesheet" href="/css/bootstrap.min.css"> |
| |
| <link rel="stylesheet" href="/css/fonts.css" type="text/css"> |
| |
| <link rel="stylesheet" href="/css/main.css"> |
| <link rel="stylesheet" href="/css/header.css"> |
| <link rel="stylesheet" href="/css/footer.css"> |
| <link rel="stylesheet" href="/css/syntax.css"> |
| <link rel="stylesheet" href="/css/docs.css"> |
| |
| <script type="text/x-mathjax-config"> |
| MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},showMathMenu:false,showMathMenuMSIE:false,showProcessingMessages:false}); |
| </script> |
| |
| <!-- original source: https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMX_HTML-full --> |
| <script type="text/javascript" src="/js/MathJax.js?config=TeX-AMS_HTML"></script> |
| |
| <!-- original source: https://code.jquery.com/jquery.min.js --> |
| <script src="/js/jquery.min.js"></script> |
| |
| <!-- original source: https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js --> |
| <script src="/js/bootstrap.min.js"></script> <!-- 3.2.0--> |
| <!-- End _include/site_head.html --> |
| |
| </head> |
| |
| <body> |
| <!-- Start _include/nav_bar.html --> |
| <div class="navbar navbar-inverse navbar-static-top ds-nav"> |
| <div class="container"> |
| <div class="navbar-header"> |
| <button type="button" class="navbar-toggle" data-toggle="collapse" data-target=".navbar-collapse"> |
| <span class="sr-only">Toggle navigation</span> |
| <span class="icon-bar"></span> |
| <span class="icon-bar"></span> |
| <span class="icon-bar"></span> |
| </button> |
| <a href="/" style="padding-top: 0px; padding-bottom: 0px;"> |
| <span class="ds-small-h-logo"></span></a> |
| </div> |
| <div class="navbar-collapse collapse"> |
| <ul class="nav navbar-nav navbar-right"> |
| <li> |
| <a href="/docs/Background/TheChallenge.html"> |
| <span class="fa fa-info-circle"></span> DOCUMENTATION</a> |
| </li> |
| <li> |
| <a href="/docs/Community/Downloads.html"> |
| <span class="fa fa-download"></span> DOWNLOAD</a> |
| </li> |
| <!-- |
| <li> |
| <a href="/docs/Architecture/Components.html"> |
| <span class="fa fa-github"></span> GITHUB</a> |
| </li> |
| --> |
| <li> |
| <a href="/docs/Community/Research.html"> |
| <span class="fa fa-paper-plane"></span> RESEARCH</a> |
| </li> |
| <li> |
| <a href="/docs/Community/index.html" style="padding-top: 0; padding-bottom: 0;"> |
| <img class="ds-small-man" src="/img/datasketches-ManWhite.svg"/>COMMUNITY</a> |
| </li> |
| <li> |
| <ul class="nav navbar-nav navbar-right ds-nav"> |
| <li class="dropdown ds-nav" > |
| <a href="#" class="dropdown-toggle" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false" style="padding-top: 0; padding-bottom: 0;"><img class="apache-logo" src="/img/feather.svg"/>Apache <span class="caret"></span></a> |
| <ul class="dropdown-menu ds-nav"> |
| <li><a href="https://www.apache.org/" target="_blank">Foundation</a></li> |
| <li><a href="https://www.apache.org/events/current-event" target="_blank">Events</a></li> |
| <li><a href="https://www.apache.org/licenses/" target="_blank">License</a></li> |
| <li><a href="https://privacy.apache.org/policies/privacy-policy-public.html" target="_blank">Privacy Policy</a></li> |
| <li><a href="https://www.apache.org/foundation/thanks.html" target="_blank">Thanks</a></li> |
| <li><a href="https://www.apache.org/security/" target="_blank">Security</a></li> |
| <li><a href="https://www.apache.org/foundation/sponsorship.html" target="_blank">Sponsorship</a></li> |
| </ul> |
| </li> |
| </ul> |
| </li> |
| </ul> |
| </div> |
| </div> |
| </div> |
| <!-- End _include/nav_bar.html --> |
| |
| |
| <!-- Start _include/javadocs.html --> |
| <div class="ds-header"> |
| <div class="container"> |
| <h4>API Snapshots: |
| <a href="https://apache.github.io/datasketches-java/4.2.0/">Java Core</a>, |
| <a href="https://apache.github.io/datasketches-cpp/5.0.0/">C++ Core</a>, |
| <a href="https://apache.github.io/datasketches-python/main/">Python</a>, |
| <a href="https://apache.github.io/datasketches-memory/master/">Memory</a>, |
| <a href="/api/pig/snapshot/apidocs/index.html">Pig</a>, |
| <a href="/api/hive/snapshot/apidocs/index.html">Hive</a>, |
| </h4> |
| </div> |
| </div> |
| <!-- End _include/javadocs.html --> |
| |
| |
| <div class="container"> |
| <div class="row"> |
| <!-- Start ToC Block --> |
| <div class="col-md-3"> |
| <div class="searchbox" style="position:relative"> |
| <gcse:searchbox-only></gcse:searchbox-only> |
| </div> |
| <!-- Start _includes/toc.html --> |
| <!-- Computer Generated File, Do Not Edit! --> |
| <link rel="stylesheet" href="/css/toc.css"> |
| <div id="toc" class="nav toc hidden-print"> |
| |
| <p id="background"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_background">Background</a> |
| </p> |
| <div class="collapse" id="collapse_background"> |
| <li><a href="/docs/Background/TheChallenge.html">•The Challenge</a></li> |
| <li><a href="/docs/Background/SketchOrigins.html">•Sketch Origins</a></li> |
| <li><a href="/docs/Background/SketchElements.html">•Sketch Elements</a></li> |
| <li><a href="/docs/Background/Presentations.html">•Presentations</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches_deck.pdf">•Overview Slide Deck</a></li> |
| </div> |
| |
| <p id="architecture-and-design"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_architecture_and_design">Architecture And Design</a> |
| </p> |
| <div class="collapse" id="collapse_architecture_and_design"> |
| <li><a href="/docs/Architecture/MajorSketchFamilies.html">•The Major Sketch Families</a></li> |
| <li><a href="/docs/Architecture/LargeScale.html">•Large Scale Computing</a></li> |
| <li><a href="/docs/Architecture/KeyFeatures.html">•Key Features</a></li> |
| <li><a href="/docs/Architecture/SketchFeaturesMatrix.html">•Sketch Features Matrix</a></li> |
| <li><a href="/docs/Architecture/Components.html">•Components</a></li> |
| <li><a href="/docs/Architecture/SketchesByComponent.html">•Sketches by Component</a></li> |
| <li><a href="/docs/Architecture/SketchCriteria.html">•Sketch Criteria</a></li> |
| |
| <p id="memory-component"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_memory_component">Memory Component</a> |
| </p> |
| <div class="collapse" id="collapse_memory_component"> |
| <li><a href="/docs/Memory/MemoryComponent.html">•Memory Component</a></li> |
| <li><a href="/docs/Memory/MemoryPerformance.html">•Memory Component Performance</a></li> |
| </div> |
| <li><a href="/docs/Architecture/OrderSensitivity.html">•Notes on Order Sensitivity</a></li> |
| <li><a href="/docs/Architecture/Concurrency.html">•Notes on Concurrency</a></li> |
| </div> |
| |
| <p id="sketch-families"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sketch_families">Sketch Families</a> |
| </p> |
| <div class="collapse" id="collapse_sketch_families"> |
| |
| <p id="distinct-counting"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_distinct_counting">Distinct Counting</a> |
| </p> |
| <div class="collapse" id="collapse_distinct_counting"> |
| <li><a href="/docs/DistinctCountFeaturesMatrix.html">•Features Matrix</a></li> |
| <li><a href="/docs/DistinctCountMeritComparisons.html">•Figures-of-Merit Comparison</a></li> |
| |
| <p id="cpc-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_cpc_sketches">CPC Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_cpc_sketches"> |
| <li><a href="/docs/CPC/CPC.html">•CPC Sketch</a></li> |
| <li><a href="/docs/CPC/CpcPerformance.html">•CPC Sketch Performance</a></li> |
| |
| <p id="cpc-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_cpc_examples">CPC Examples</a> |
| </p> |
| <div class="collapse" id="collapse_cpc_examples"> |
| <li><a href="/docs/CPC/CpcJavaExample.html">•CPC Sketch Java Example</a></li> |
| <li><a href="/docs/CPC/CpcCppExample.html">•CPC Sketch C++ Example</a></li> |
| <li><a href="/docs/CPC/CpcPigExample.html">•CPC Sketch Pig UDFs</a></li> |
| <li><a href="/docs/CPC/CpcHiveExample.html">•CPC Sketch Hive UDFs</a></li> |
| </div> |
| </div> |
| |
| <p id="hyperloglog-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hyperloglog_sketches">HyperLogLog Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_hyperloglog_sketches"> |
| <li><a href="/docs/HLL/HLL.html">•HLL Sketch</a></li> |
| <li><a href="/docs/HLL/HllMap.html">•HLL Map Sketch</a></li> |
| |
| <p id="hll-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hll_examples">HLL Examples</a> |
| </p> |
| <div class="collapse" id="collapse_hll_examples"> |
| <li><a href="/docs/HLL/HllJavaExample.html">•HLL Sketch Java Example</a></li> |
| <li><a href="/docs/HLL/HllCppExample.html">•HLL Sketch C++ Example</a></li> |
| <li><a href="/docs/HLL/HllPigUDFs.html">•HLL Sketch Pig UDFs</a></li> |
| <li><a href="/docs/HLL/HllHiveUDFs.html">•HLL Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="hll-studies"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_hll_studies">HLL Studies</a> |
| </p> |
| <div class="collapse" id="collapse_hll_studies"> |
| <li><a href="/docs/HLL/HllPerformance.html">•HLL Sketch Performance</a></li> |
| <li><a href="/docs/HLL/Hll_vs_CS_Hllpp.html">•HLL vs Clearspring HLL++</a></li> |
| <li><a href="/docs/HLL/HllSketchVsDruidHyperLogLogCollector.html">•HLL Sketch vs Druid HyperLogLogCollector</a></li> |
| </div> |
| </div> |
| |
| <p id="theta-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_sketches">Theta Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_theta_sketches"> |
| <li><a href="/docs/Theta/ThetaSketchFramework.html">•Theta Sketch Framework</a></li> |
| |
| <p id="theta-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_examples">Theta Examples</a> |
| </p> |
| <div class="collapse" id="collapse_theta_examples"> |
| <li><a href="/docs/Theta/ConcurrentThetaSketch.html">•Concurrent Theta Sketch</a></li> |
| <li><a href="/docs/Theta/ThetaJavaExample.html">•Theta Sketch Java Example</a></li> |
| <li><a href="/docs/Theta/ThetaSparkExample.html">•Theta Sketch Spark Example</a></li> |
| <li><a href="/docs/Theta/ThetaPigUDFs.html">•Theta Sketch Pig UDFs</a></li> |
| <li><a href="/docs/Theta/ThetaHiveUDFs.html">•Theta Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="kmv-tutorial"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_kmv_tutorial">KMV Tutorial</a> |
| </p> |
| <div class="collapse" id="collapse_kmv_tutorial"> |
| <li><a href="/docs/Theta/InverseEstimate.html">•The Inverse Estimate</a></li> |
| <li><a href="/docs/Theta/KMVempty.html">•Empty Sketch</a></li> |
| <li><a href="/docs/Theta/KMVfirstEst.html">•First Estimator</a></li> |
| <li><a href="/docs/Theta/KMVbetterEst.html">•Better Estimator</a></li> |
| <li><a href="/docs/Theta/KMVrejection.html">•Rejection Rules</a></li> |
| <li><a href="/docs/Theta/KMVupdateVkth.html">•Update V(kth) Rule</a></li> |
| </div> |
| |
| <p id="set-operations-and-p-sampling"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_set_operations_and_p-sampling">Set Operations and P-sampling</a> |
| </p> |
| <div class="collapse" id="collapse_set_operations_and_p-sampling"> |
| <li><a href="/docs/Theta/ThetaSketchSetOps.html">•Set Operations</a></li> |
| <li><a href="/docs/Theta/ThetaSetOpsCornerCases.html">•Model & Test Set Operations</a></li> |
| <li><a href="/docs/Theta/ThetaPSampling.html">•<i>p</i>-Sampling</a></li> |
| </div> |
| |
| <p id="accuracy"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_accuracy">Accuracy</a> |
| </p> |
| <div class="collapse" id="collapse_accuracy"> |
| <li><a href="/docs/Theta/ThetaAccuracy.html">•Basic Accuracy</a></li> |
| <li><a href="/docs/Theta/ThetaAccuracyPlots.html">•Accuracy Plots</a></li> |
| <li><a href="/docs/Theta/ThetaErrorTable.html">•Relative Error Table</a></li> |
| <li><a href="/docs/Theta/ThetaSketchSetOpsAccuracy.html">•SetOp Accuracy</a></li> |
| <li><a href="/docs/Theta/AccuracyOfDifferentKUnions.html">•Unions With Different k</a></li> |
| </div> |
| |
| <p id="size"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_size">Size</a> |
| </p> |
| <div class="collapse" id="collapse_size"> |
| <li><a href="/docs/Theta/ThetaSize.html">•Theta Sketch Size</a></li> |
| </div> |
| |
| <p id="speed"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_speed">Speed</a> |
| </p> |
| <div class="collapse" id="collapse_speed"> |
| <li><a href="/docs/Theta/ThetaUpdateSpeed.html">•Update Speed</a></li> |
| <li><a href="/docs/Theta/ThetaMergeSpeed.html">•Merge Speed</a></li> |
| </div> |
| |
| <p id="theta-sketch-theory"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_theta_sketch_theory">Theta Sketch Theory</a> |
| </p> |
| <div class="collapse" id="collapse_theta_sketch_theory"> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchFramework.pdf">•Theta Sketch Framework (PDF)</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/ThetaSketchEquations.pdf">•Theta Sketch Equations (PDF)</a></li> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/DataSketches.pdf">•DataSketches (PDF)</a></li> |
| <li><a href="/docs/Theta/ThetaConfidenceIntervals.html">•Confidence Intervals Notes</a></li> |
| <li><a href="/docs/Theta/ThetaMergingAlgorithm.html">•Merging Algorithm Notes</a></li> |
| <li><a href="/docs/Theta/ThetaReferences.html">•Theta References</a></li> |
| </div> |
| </div> |
| |
| <p id="tuple-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_tuple_sketches">Tuple Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_tuple_sketches"> |
| <li><a href="/docs/Tuple/TupleOverview.html">•Tuple Overview</a></li> |
| |
| <p id="tuple-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_tuple_examples">Tuple Examples</a> |
| </p> |
| <div class="collapse" id="collapse_tuple_examples"> |
| <li><a href="/docs/Tuple/TupleJavaExample.html">•Tuple Java Example</a></li> |
| <li><a href="/docs/Tuple/TupleEngagementExample.html">•Tuple Engagement Example</a></li> |
| <li><a href="/docs/Tuple/TuplePigUDFs.html">•Tuple Pig UDFs</a></li> |
| <li><a href="/docs/Tuple/TupleHiveUDFs.html">•Tuple Hive UDFs</a></li> |
| </div> |
| </div> |
| </div> |
| |
| <p id="most-frequent"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_most_frequent">Most Frequent</a> |
| </p> |
| <div class="collapse" id="collapse_most_frequent"> |
| <li><a href="/docs/Frequency/FrequencySketchesOverview.html">•Frequency Sketches Overview</a></li> |
| |
| <p id="frequent-item-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_item_sketches">Frequent Item Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_frequent_item_sketches"> |
| <li><a href="/docs/Frequency/FrequentItemsOverview.html">•Frequent Items Overview</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsErrorTable.html">•Frequent Items Error Table</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsReferences.html">•Frequent Items References</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsPerformance.html">•Frequent Items Performance</a></li> |
| |
| <p id="most-frequent-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_most_frequent_examples">Most Frequent Examples</a> |
| </p> |
| <div class="collapse" id="collapse_most_frequent_examples"> |
| <li><a href="/docs/Frequency/FrequentItemsJavaExample.html">•Frequent Items Java Example</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsCppExample.html">•Frequent Items C++ Example</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsPigUDFs.html">•Frequent Items Pig UDFs</a></li> |
| <li><a href="/docs/Frequency/FrequentItemsHiveUDFs.html">•Frequent Items Hive UDFs</a></li> |
| </div> |
| </div> |
| |
| <p id="frequent-distinct-sketches"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_frequent_distinct_sketches">Frequent Distinct Sketches</a> |
| </p> |
| <div class="collapse" id="collapse_frequent_distinct_sketches"> |
| <li><a href="/docs/Frequency/FrequentDistinctTuplesSketch.html">•Frequent Distinct Tuples Sketch</a></li> |
| </div> |
| </div> |
| |
| <p id="quantiles-and-histograms"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_and_histograms">Quantiles And Histograms</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_and_histograms"> |
| <li><a href="/docs/Quantiles/SketchingQuantilesAndRanksTutorial.html">•Quantiles and Ranks Tutorial</a></li> |
| <li><a href="/docs/Quantiles/QuantilesOverview.html">•Quantiles Overview</a></li> |
| <li><a href="/docs/KLL/KLLSketch.html">•KLL Floats sketch</a></li> |
| <li><a href="/docs/KLL/KLLAccuracyAndSize.html">•KLL Sketch Accuracy and Size</a></li> |
| <li><a href="/docs/REQ/ReqSketch.html">•REQ Floats sketch</a></li> |
| <li><a href="/docs/Quantiles/OrigQuantilesSketch.html">•Original QuantilesSketch</a></li> |
| |
| <p id="quantiles-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_examples">Quantiles Examples</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_examples"> |
| <li><a href="/docs/Quantiles/QuantilesJavaExample.html">•Quantiles Sketch Java Example</a></li> |
| <li><a href="/docs/KLL/KLLCppExample.html">•KLL Quantiles Sketch C++ Example</a></li> |
| <li><a href="/docs/Quantiles/QuantilesPigUDFs.html">•Quantiles Sketch Pig UDFs</a></li> |
| <li><a href="/docs/Quantiles/QuantilesHiveUDFs.html">•Quantiles Sketch Hive UDFs</a></li> |
| </div> |
| |
| <p id="quantiles-studies"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_studies">Quantiles Studies</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_studies"> |
| <li><a href="/docs/QuantilesStudies/DruidApproxHistogramStudy.html">•Druid Approximate Histogram</a></li> |
| <li><a href="/docs/QuantilesStudies/MomentsSketchStudy.html">•Moments Sketch Study</a></li> |
| <li><a href="/docs/QuantilesStudies/QuantilesStreamAStudy.html">•Quantiles StreamA Study</a></li> |
| <li><a href="/docs/QuantilesStudies/ExactQuantiles.html">•Exact Quantiles for Studies</a></li> |
| </div> |
| |
| <p id="quantiles-sketch-theory"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_quantiles_sketch_theory">Quantiles Sketch Theory</a> |
| </p> |
| <div class="collapse" id="collapse_quantiles_sketch_theory"> |
| <li><a href="https://github.com/apache/datasketches-website/tree/master/docs/pdf/Quantiles_KLL.pdf">•Optimal Quantile Approximation in Streams</a></li> |
| <li><a href="/docs/Quantiles/QuantilesReferences.html">•Quantiles References</a></li> |
| </div> |
| </div> |
| |
| <p id="sampling"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sampling">Sampling</a> |
| </p> |
| <div class="collapse" id="collapse_sampling"> |
| <li><a href="/docs/Sampling/ReservoirSampling.html">•Reservoir Sampling</a></li> |
| <li><a href="/docs/Sampling/ReservoirSamplingPerformance.html">•Reservoir Sampling Performance</a></li> |
| <li><a href="/docs/Sampling/VarOptSampling.html">•VarOpt Sampling</a></li> |
| |
| <p id="sampling-examples"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_sampling_examples">Sampling Examples</a> |
| </p> |
| <div class="collapse" id="collapse_sampling_examples"> |
| <li><a href="/docs/Sampling/ReservoirSamplingJava.html">•Reservoir Sampling Java Example</a></li> |
| <li><a href="/docs/Sampling/ReservoirSamplingPigUDFs.html">•Reservoir Sampling Pig UDFs</a></li> |
| <li><a href="/docs/Sampling/VarOptSamplingJava.html">•VarOpt Sampling Java Example</a></li> |
| <li><a href="/docs/Sampling/VarOptPigUDFs.html">•VarOpt Sampling Pig UDFs</a></li> |
| </div> |
| </div> |
| </div> |
| |
| <p id="system-integrations"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_system_integrations">System Integrations</a> |
| </p> |
| <div class="collapse" id="collapse_system_integrations"> |
| <li><a href="/docs/SystemIntegrations/ApacheDruidIntegration.html">•Using Sketches in ApacheDruid</a></li> |
| <li><a href="/docs/SystemIntegrations/ApacheHiveIntegration.html">•Using Sketches in Apache Hive</a></li> |
| <li><a href="/docs/SystemIntegrations/ApachePigIntegration.html">•Using Sketches in Apache Pig</a></li> |
| <li><a href="/docs/SystemIntegrations/PostgreSQLIntegration.html">•Using Sketches in PostgreSQL</a></li> |
| </div> |
| |
| <p id="community"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_community">Community</a> |
| </p> |
| <div class="collapse" id="collapse_community"> |
| <li><a href="/docs/Community/index.html">•Community</a></li> |
| <li><a href="/docs/Community/Downloads.html">•Downloads</a></li> |
| <li><a href="/docs/Community/NewCommitterProcess.html">•Committer Process</a></li> |
| <li><a href="/docs/Community/ReleaseProcessForCppComponents.html">•Release Process For CPP Components</a></li> |
| <li><a href="/docs/Community/ReleaseProcessForJavaComponents.html">•Release Process For Java Components</a></li> |
| <li><a href="/docs/Community/Transitioning.html">•Transitioning from prior GitHub Site</a></li> |
| </div> |
| |
| <p id="research"> |
| <a data-toggle="collapse" class="menu collapsed" href="#collapse_research">Research</a> |
| </p> |
| <div class="collapse" id="collapse_research"> |
| <li><a href="/docs/Community/Research.html">•Research</a></li> |
| </div> |
| </div> |
| <!-- End _includes/toc.html --> |
| |
| |
| <!-- Start _includes/tocScript.html --> |
| <script> |
| (function () { |
| |
| var findLineItem = function (path) { |
| return document.querySelector(`#toc [href="${path}"]`); |
| }; |
| |
| function findNavItem(path) { |
| return document.querySelector(`.nav [href="${path}"]`); |
| } |
| |
| var highlighLineItem = function (element) { |
| element.classList.add('highlight'); |
| }; |
| |
| var checkHasClass = function (element, className) { |
| return element.className.split(' ').find(function (item) { return item === className || '' }) |
| } |
| |
| var findAllCollapseParents = function (element) { |
| var collapseMenus = []; |
| var elementPointer = element; |
| while (elementPointer !== document.body) { |
| if (checkHasClass(elementPointer, 'collapse')) { |
| collapseMenus.push(elementPointer); |
| } |
| elementPointer = elementPointer.parentElement |
| } |
| return collapseMenus |
| }; |
| |
| var openMenuItem = function (element) { |
| // $(element).collapse('show') would start a transition, adding `in` class instead. |
| element.classList.add('in'); |
| }; |
| |
| var openAllFromList = function (elementList) { |
| elementList.forEach(openMenuItem); |
| }; |
| |
| var highlightAndOpenMenu = function () { |
| // Highlight & expand nav item in the TOC |
| var currentLineItem = findLineItem(document.location.pathname); |
| highlighLineItem(currentLineItem); |
| openAllFromList(findAllCollapseParents(currentLineItem)); |
| |
| // Highlight nav item in top navigation |
| highlighLineItem(findNavItem(document.location.pathname)); |
| }; |
| |
| $(highlightAndOpenMenu); |
| |
| }()); |
| </script> |
| <!-- End _includes/tocScript.html --> |
| |
| </div> |
| <!-- End ToC Block --> |
| <div class="col-md-9 doc-content"> |
| <!-- |
| 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. |
| --> |
| <h2 id="memory-component">Memory Component</h2> |
| |
| <h3 id="introduction">Introduction</h3> |
| |
| <p>The primary objective for the <em>Memory Component</em> is to allow high-performance read-write access to Java “off-heap” memory |
| (also referred to as <em>direct</em>, or <em>native</em> memory). However, as documented below, this component has a rich set of other |
| capabilities as well.</p> |
| |
| <h4 id="versioning">Versioning</h4> |
| <p>The <em>DataSketches</em> memory component has its own repository and is released with its own jars in <em>Maven Central</em> |
| (groupId=org.apache.datasketches, artifactId=datasketches-memory). |
| This document applies to the memory component versions 0.10.0 and after.</p> |
| |
| <h4 id="naming-conventions">Naming Conventions</h4> |
| <p>To avoid confusion in the documentation the capitalized <em>Memory</em> refers to the code in the |
| Java <em>org.apache.datasketches.memory</em> component, and the uncapitalized <em>memory</em> refers to computer memory in general. |
| There is also a class <em>org.apache.datasketches.memory.Memory</em> that should not be confused with the <em>org.apache.datasketches.memory</em> component. |
| In the text, sometimes <em>Memory</em> refers to the entire component and sometimes to the specific class, |
| but it should be clear from the context.</p> |
| |
| <p>For compatibility and ease-of-use the <em>Memory</em> API can also be used to manage data structures that are |
| contained in Java on-heap primitive arrays, memory mapped files, or <em>ByteBuffers</em>.</p> |
| |
| <h4 id="driving-rationale-large-java-systems-require-off-heap-memory">Driving Rationale: Large Java Systems Require “Off-Heap” Memory</h4> |
| <p>The hardware systems used in big data environments can be quite large approaching a terabyte |
| of RAM and 24 or more CPUs, each of which can manage two threads. |
| Most of that memory is usually dedicated to selected partitions of data, |
| which can even be orders of magnitude larger. |
| How the system designers select the partitions of the data to be in RAM over time is quite complex |
| and varies considerably based on the specific objectives of the systems platform.</p> |
| |
| <p>In these very large data environments managing how the data gets copied into RAM, |
| when it is considered obsolete, and when it can be written |
| over by newer or different partitions of data, are important aspects of the systems design. |
| Having the JVM manage these large chunks of memory is often problematic. |
| For example, the Java specification requires that a new allocation of memory be cleared before |
| it can be used. When the allocations become large this alone can result in large pauses in a |
| running application, especially if the application does not require that the memory be cleared. |
| Repeated allocation and deallocation of large memory blocks can also cause large garbage collection pauses, |
| which can have major impact on the performance of real-time systems. |
| As a result, it is often the case that the system designers need to manage these large chunks of |
| memory directly.</p> |
| |
| <p>The JVM has a very sophisticated heap management process and works very well for many |
| general purpose programming tasks. |
| However, for very large systems that have critical latency requirements, |
| utilizing off-heap memory efficiently becomes a requirement.</p> |
| |
| <p>Java does not permit normal java processes direct access to off-heap memory (except as noted below). Nonetheless, |
| in order to improve performance, many internal Java classes leverage a low-level, restricted |
| class called (unfortunately) “<em>Unsafe</em>”, which does exactly that. The methods of <em>Unsafe</em> |
| are native methods that are initially compiled into C++ code. The JIT compiler |
| replaces this C++ code with assembly language instructions called “intrinsics”, which |
| can be just a single CPU instruction. This results in superior runtime performance that is |
| very close to what could be achieved if the application was written in C++.</p> |
| |
| <p>The <em>Memory</em> component is essentially an extension of <em>Unsafe</em> and wraps most of the |
| primitive get and put methods and a few specialized methods into a convenient API |
| organized around an allocated block of native memory.</p> |
| |
| <p>The only “official” alternative available to systems developers is to use the Java <em>ByteBuffer</em> class |
| that also allows access to off-heap memory. However, the <em>ByteBuffer</em> API is extremely limited |
| and contains serious defects in its design and traps that many users of the <em>ByteBuffer</em> class unwittingly |
| fall into, which results in corrupted data. This <em>Memory Component</em> has been designed to be a |
| replacement for the <em>ByteBuffer</em> class.</p> |
| |
| <p>Using the <em>Memory</em> component cannot be taken lightly, as the systems developer must now be |
| aware of the importance of memory allocation and deallocation and make sure these resources |
| are managed properly. To the extent possible, this <em>Memory Component</em> has been designed leveraging Java’s own |
| <em>AutoCloseable</em>, and <em>Cleaner</em> and also tracks when allocated memory has been freed and provides safety checks |
| against the dreaded “use-after-free” case.</p> |
| |
| <h3 id="architecture">Architecture</h3> |
| <p>The Memory component is designed around two major types of entities:</p> |
| |
| <ul> |
| <li><em>Resources</em>: A <em>Resource</em> is a collection of consecutive bytes.</li> |
| <li><em>APIs</em>: An API is a programming interface for reading and writing to a resource.</li> |
| </ul> |
| |
| <h4 id="resourses">Resourses</h4> |
| <p>The <em>Memory</em> component defines 4 <em>Resources</em>, which at their most basic level can be viewed as a collection of consecutive bytes.</p> |
| |
| <ul> |
| <li>Primitive on-heap arrays: <em>boolean[], byte[], char[], short[], int[], long[], float[], double[]</em>.</li> |
| <li>Java <em>ByteBuffers</em>.</li> |
| <li>Off-heap memory. Also called “native” or “direct” memory.</li> |
| <li>Memory-mapped files.</li> |
| </ul> |
| |
| <p>It should be noted at the outset that the off-heap memory and the memory-mapped file resources require special handling with respect to allocation and deallocation. |
| The <em>Memory Component</em> has been designed to access these resources leveraging the Java <em>AutoCloseable</em> interface and the Java internal <em>Cleaner</em> class, |
| which also provides the JVM with mechanisms for tracking overall use of off-heap memory.</p> |
| |
| <h4 id="apis">APIs</h4> |
| <p>The <em>Memory</em> component defines 5 principal APIs for accessing the above resources.</p> |
| |
| <ul> |
| <li><em>Memory</em>: Read-only access using byte offsets from the start of the resource.</li> |
| <li><em>WritableMemory</em>: Read/write access using byte offsets from the start of the resource.</li> |
| <li><em>BaseBuffer</em>: Positional API that supports <em>Buffer</em> and <em>WritableBuffer</em> using four key positional values: |
| <em>start</em>, <em>position</em>, <em>end</em>, and <em>capacity</em>, and a rich set of methods to access them.</li> |
| <li><em>Buffer</em>: Read-only access using the <em>BaseBuffer</em> positional API.</li> |
| <li><em>WritableBuffer</em>: Read-write access using the <em>BaseBuffer</em> positional API.</li> |
| </ul> |
| |
| <p>These 5 principal APIs and the four Resources are then multiplexed into 32 API/Resource combinations as follows:</p> |
| |
| <ul> |
| <li>Resource: on-heap, <em>ByteBuffer</em>, off-heap, memory-mapped files.</li> |
| <li>Memory versus Buffer APIs</li> |
| <li>Read-only versus read-write APIs</li> |
| <li>Little-Endian versus Big-Endian APIs for multibyte primitives</li> |
| </ul> |
| |
| <h4 id="design-goals">Design Goals</h4> |
| <p>These are the major design goals for the <em>Memory Component</em>.</p> |
| |
| <ul> |
| <li><strong>Common API</strong>. The APIs should be agnostic to the chosen resource, with only a few minor exceptions.</li> |
| <li><strong>Performance is critical</strong>. The architecture has been specifically designed to eliminate unnecessary object and interface redirection. |
| This allows the JIT compiler to collapse abstract hierarchies down to a “base class” at runtime, eliminating all call overhead. |
| This is why the “APIs” are defined using abstract class hierarchies versus using interfaces, which would force the JIT compiler to create |
| virtual jump tables in the emitted code. This has been proven to provide substantial improvement in runtime performance.</li> |
| <li><strong>Eliminate unnecessary copies</strong>. This is also a performance goal. All the API access classes are essentially “views” into the underlying resource. |
| For example: switching from a “Buffer” API to a “Memory” API, or from a writable API to a read-only API, or from a big-endian to a little-endian |
| view of the resource does not involve any copying or movement of the underlying data.</li> |
| <li><strong>Data type agnostic</strong>. Contrary to the Java specification, the underlying resource can be simultaneously viewed as a collection of bytes, ints, longs, etc, at arbitrary byte offsets. This is similar to the <em>union</em> construct in C. The <em>ByteBuffer</em> already allows this, but its implementation is limited and flawed.</li> |
| <li><strong>Efficient read-only vs read-write implementation</strong>. To eliminate duplicate code and unnecessary exceptions we have the writable API extend the read-only API. |
| This means that the read-only API has no writable methods, thus accidental writing from this API is not possible. Given a writable instance, |
| converting it to a read-only instance is a simple cast at compile time. It also means that a user could intentionally down-cast a read-only instance into a writable instance. It has been our experience, however, that this is very rare, and usually only used to obtain an attribute that would otherwise only be obtainable from the writable interface, such as a reference to the underlying array object. For example, this is used internally within our library to eliminate unnecessary data copies during serialization.</li> |
| <li><strong>Endianness is immutable and remembered when switching views</strong>. This was an intentional design choice in response to the way the <em>ByteBuffer</em> was designed, |
| which allows the user to change endianness dynamically. We have found the <em>ByteBuffer</em> implementation to be a major source of data corruption problems that have proven to be nearly impossible to fix.</li> |
| <li><strong>Provide both absolute offset addressing and relative positional addressing</strong>. The <em>Memory</em> hierarchy provides the absolute offset addressing API and the |
| <em>Buffer</em> hierarchy provides the relative postional addressing API. These two addressing mechanisms can be switched back and forth without changing the fundamental connection to the |
| underlying resource.</li> |
| <li><strong>Regional views</strong>. Any resource can be subdivided into smaller <em>regions</em>. This is similar to the <em>ByteBuffer.slice()</em> capability except it is more flexible.</li> |
| </ul> |
| |
| <h4 id="diagram-of-the-core-hierarchy">Diagram of the Core Hierarchy</h4> |
| <p>This includes both package-private classes as well as public classes, but should help the user understand the inner workings of the <em>Memory Component</em>.</p> |
| |
| <p><img class="doc-img-full" src="/docs/img/memory/CoreHierarchy.png" alt="CoreHierarchy.png" /></p> |
| |
| <h3 id="mapping-a-resource-to-an-api">Mapping a Resource to an API</h3> |
| <p>There are two different ways to map a resource to an API.</p> |
| |
| <ul> |
| <li>The first uses methods for allocating on-heap arrays or heap or direct <em>ByteBuffers</em>.</li> |
| <li>The second way to map a resource to an API is for <em>AutoCloseable</em> resources, such as off-heap memory and memory-mapped files. |
| Special classes called “<em>Handles</em>” are used to manage the <em>AutoCloseable</em> properties.</li> |
| </ul> |
| |
| <h4 id="examples-for-accessing-primitive-on-heap-array-resources">Examples for Accessing Primitive On-heap Array Resources</h4> |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="c1">//use static methods to map a new array of 1024 bytes to the WritableMemory API</span> |
| <span class="nc">WritableMemory</span> <span class="n">wmem</span> <span class="o">=</span> <span class="nc">WritableMemory</span><span class="o">.</span><span class="na">allocate</span><span class="o">(</span><span class="mi">1024</span><span class="o">);</span> |
| |
| <span class="c1">//Or by wrapping an existing primitive array:</span> |
| <span class="kt">byte</span><span class="o">[]</span> <span class="n">array</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">byte</span><span class="o">[]</span> <span class="o">{</span><span class="mi">1</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="mi">2</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="mi">0</span><span class="o">};</span> |
| <span class="nc">Memory</span> <span class="n">mem</span> <span class="o">=</span> <span class="nc">Memory</span><span class="o">.</span><span class="na">wrap</span><span class="o">(</span><span class="n">array</span><span class="o">);</span> |
| <span class="k">assert</span> <span class="n">mem</span><span class="o">.</span><span class="na">getInt</span><span class="o">(</span><span class="mi">0</span><span class="o">)</span> <span class="o">==</span> <span class="mi">1</span><span class="o">;</span> |
| <span class="k">assert</span> <span class="n">mem</span><span class="o">.</span><span class="na">getInt</span><span class="o">(</span><span class="mi">4</span><span class="o">)</span> <span class="o">==</span> <span class="mi">2</span><span class="o">;</span> |
| </code></pre></div></div> |
| |
| <p>The following illustrates that the underlying structure of the resource is <em>bytes</em> but we can read it as |
| <em>ints, longs, char</em>, or whatever. This is similar to a C <em>UNION</em>, which allows multiple data types |
| to access the underlying bytes. This isn’t allowed in Java! |
| So you have to keep careful track of your own structure and the appropriate byte offsets. For example:</p> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="kt">byte</span><span class="o">[]</span> <span class="n">arr</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">byte</span><span class="o">[</span><span class="mi">16</span><span class="o">];</span> |
| <span class="nc">WritableMemory</span> <span class="n">wmem</span> <span class="o">=</span> <span class="nc">WritableMemory</span><span class="o">.</span><span class="na">writableWrap</span><span class="o">(</span><span class="n">arr</span><span class="o">);</span> |
| <span class="n">wmem</span><span class="o">.</span><span class="na">putByte</span><span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="o">(</span><span class="kt">byte</span><span class="o">)</span> <span class="mi">1</span><span class="o">);</span> |
| <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">wmem</span><span class="o">.</span><span class="na">getInt</span><span class="o">(</span><span class="mi">0</span><span class="o">);</span> |
| <span class="k">assert</span> <span class="o">(</span> <span class="n">v</span> <span class="o">==</span> <span class="mi">256</span> <span class="o">);</span> |
| |
| <span class="n">arr</span><span class="o">[</span><span class="mi">9</span><span class="o">]</span> <span class="o">=</span> <span class="mi">3</span><span class="o">;</span> <span class="c1">//you can also access the backing array directly</span> |
| <span class="kt">long</span> <span class="n">v2</span> <span class="o">=</span> <span class="n">wmem</span><span class="o">.</span><span class="na">getLong</span><span class="o">(</span><span class="mi">8</span><span class="o">);</span> |
| <span class="k">assert</span> <span class="o">(</span> <span class="n">v2</span> <span class="o">==</span> <span class="mi">768L</span><span class="o">);</span> |
| </code></pre></div></div> |
| |
| <p>Reading and writing multibyte primitives requires an assumption about byte ordering or <em>endianness</em>. |
| The default endianness is <em>ByteOrder.nativeOrder()</em>, which for most CPUs is <em>ByteOrder.LITTLE_ENDIAN</em>. |
| Additional APIs are also available for reading and writing in non-native endianness.</p> |
| |
| <p>All of the APIs provide a useful <em>toHexString(…)</em> method to assist you in viewing the data in your resources.</p> |
| |
| <h4 id="examples-for-accessing-bytebuffers">Examples for Accessing ByteBuffers</h4> |
| <p>Mapping a <em>ByteBuffer</em> resource to the <em>WritableMemory</em> API.<br /> |
| Here we write the <em>WritableBuffer</em> and read from both the <em>ByteBuffer</em> and the <em>WritableBuffer</em>.</p> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nd">@Test</span> |
| <span class="kd">public</span> <span class="kt">void</span> <span class="nf">simpleBBTest</span><span class="o">()</span> <span class="o">{</span> |
| <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1024</span><span class="o">;</span> <span class="c1">//longs</span> |
| <span class="kt">byte</span><span class="o">[]</span> <span class="n">arr</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">byte</span><span class="o">[</span><span class="n">n</span> <span class="o">*</span> <span class="mi">8</span><span class="o">];</span> |
| <span class="nc">ByteBuffer</span> <span class="n">bb</span> <span class="o">=</span> <span class="nc">ByteBuffer</span><span class="o">.</span><span class="na">wrap</span><span class="o">(</span><span class="n">arr</span><span class="o">);</span> |
| <span class="n">bb</span><span class="o">.</span><span class="na">order</span><span class="o">(</span><span class="nc">ByteOrder</span><span class="o">.</span><span class="na">nativeOrder</span><span class="o">());</span> |
| |
| <span class="nc">WritableBuffer</span> <span class="n">wbuf</span> <span class="o">=</span> <span class="nc">WritableBuffer</span><span class="o">.</span><span class="na">writableWrap</span><span class="o">(</span><span class="n">bb</span><span class="o">);</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> <span class="c1">//write to wbuf</span> |
| <span class="n">wbuf</span><span class="o">.</span><span class="na">putLong</span><span class="o">(</span><span class="n">i</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="n">wbuf</span><span class="o">.</span><span class="na">resetPosition</span><span class="o">();</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> <span class="c1">//read from wbuf</span> |
| <span class="kt">long</span> <span class="n">v</span> <span class="o">=</span> <span class="n">wbuf</span><span class="o">.</span><span class="na">getLong</span><span class="o">();</span> |
| <span class="n">assertEquals</span><span class="o">(</span><span class="n">v</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> <span class="c1">//read from BB</span> |
| <span class="kt">long</span> <span class="n">v</span> <span class="o">=</span> <span class="n">bb</span><span class="o">.</span><span class="na">getLong</span><span class="o">();</span> |
| <span class="n">assertEquals</span><span class="o">(</span><span class="n">v</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| </code></pre></div></div> |
| |
| <h4 id="accessing-autocloseable-resources">Accessing <em>AutoCloseable</em> Resources</h4> |
| |
| <p>The following diagram illustrates the relationships between the <em>Map</em> and <em>Handle</em> hierarchies. |
| The <em>Map</em> interfaces are not public, nonetheless this should help understand their function.</p> |
| |
| <p><img class="doc-img-full" src="/docs/img/memory/MapAndHandleHierarchy.png" alt="MapAndHandleHierarchy.png" /></p> |
| |
| <h5 id="accessing-off-heap-resources">Accessing Off-Heap Resources</h5> |
| <p>Direct allocation of off-heap resources requires that the resource be closed when finished. |
| This is accomplished using a <em>WritableDirectHandle</em> that implements the Java <em>AutoCloseable</em> interface. |
| Note that this example leverages the try-with-resources statement to properly close the resource.</p> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nd">@Test</span> |
| <span class="kd">public</span> <span class="kt">void</span> <span class="nf">simpleAllocateDirect</span><span class="o">()</span> <span class="kd">throws</span> <span class="nc">Exception</span> <span class="o">{</span> |
| <span class="kt">int</span> <span class="n">longs</span> <span class="o">=</span> <span class="mi">32</span><span class="o">;</span> |
| <span class="k">try</span> <span class="o">(</span><span class="nc">WritableHandle</span> <span class="n">wh</span> <span class="o">=</span> <span class="nc">WritableMemory</span><span class="o">.</span><span class="na">allocateDirect</span><span class="o">(</span><span class="n">longs</span> <span class="o"><<</span> <span class="mi">3</span><span class="o">))</span> <span class="o">{</span> |
| <span class="nc">WritableMemory</span> <span class="n">wMem1</span> <span class="o">=</span> <span class="n">wh</span><span class="o">.</span><span class="na">getWritable</span><span class="o">();</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span><span class="o"><</span><span class="n">longs</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> |
| <span class="n">wMem1</span><span class="o">.</span><span class="na">putLong</span><span class="o">(</span><span class="n">i</span> <span class="o"><<</span> <span class="mi">3</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span> |
| <span class="n">assertEquals</span><span class="o">(</span><span class="n">wMem1</span><span class="o">.</span><span class="na">getLong</span><span class="o">(</span><span class="n">i</span> <span class="o"><<</span> <span class="mi">3</span><span class="o">),</span> <span class="n">i</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| </code></pre></div></div> |
| |
| <p>Note that these direct allocations can be larger than 2GB.</p> |
| |
| <h5 id="memory-mapped-file-resources">Memory Mapped File Resources</h5> |
| <p>Memory-mapped files are resources that also must be closed when finished. |
| This is accomplished using a <em>MapHandle</em> that implements the Java <em>AutoClosable</em> interface. |
| In the src/test/resources directory of the memory-X.Y.Z-test-sources.jar there is a file called <em>GettysburgAddress.txt</em>. |
| Note that this example leverages the <em>try-with-resources</em> statement to properly close the resource. |
| To print out Lincoln’s Gettysburg Address:</p> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nd">@Test</span> |
| <span class="kd">public</span> <span class="kt">void</span> <span class="nf">simpleMap</span><span class="o">()</span> <span class="kd">throws</span> <span class="nc">Exception</span> <span class="o">{</span> |
| <span class="nc">File</span> <span class="n">file</span> <span class="o">=</span> <span class="k">new</span> <span class="nc">File</span><span class="o">(</span><span class="n">getClass</span><span class="o">().</span><span class="na">getClassLoader</span><span class="o">().</span><span class="na">getResource</span><span class="o">(</span><span class="s">"GettysburgAddress.txt"</span><span class="o">).</span><span class="na">getFile</span><span class="o">());</span> |
| <span class="k">try</span> <span class="o">(</span><span class="nc">MapHandle</span> <span class="n">h</span> <span class="o">=</span> <span class="nc">Memory</span><span class="o">.</span><span class="na">map</span><span class="o">(</span><span class="n">file</span><span class="o">))</span> <span class="o">{</span> |
| <span class="nc">Memory</span> <span class="n">mem</span> <span class="o">=</span> <span class="n">h</span><span class="o">.</span><span class="na">get</span><span class="o">();</span> |
| <span class="kt">byte</span><span class="o">[]</span> <span class="n">bytes</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">byte</span><span class="o">[(</span><span class="kt">int</span><span class="o">)</span><span class="n">mem</span><span class="o">.</span><span class="na">getCapacity</span><span class="o">()];</span> |
| <span class="n">mem</span><span class="o">.</span><span class="na">getByteArray</span><span class="o">(</span><span class="mi">0</span><span class="o">,</span> <span class="n">bytes</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="n">bytes</span><span class="o">.</span><span class="na">length</span><span class="o">);</span> |
| <span class="nc">String</span> <span class="n">text</span> <span class="o">=</span> <span class="k">new</span> <span class="nc">String</span><span class="o">(</span><span class="n">bytes</span><span class="o">);</span> |
| <span class="nc">System</span><span class="o">.</span><span class="na">out</span><span class="o">.</span><span class="na">println</span><span class="o">(</span><span class="n">text</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| </code></pre></div></div> |
| |
| <p>The following test does the following:</p> |
| |
| <ol> |
| <li>Creates a off-heap <em>WritableMemory</em> and preloads it with 4GB of consecutive longs as a candidate source.</li> |
| <li>Creates an empty file, and maps it to a memory-mapped space also of 4GB as the destination.</li> |
| <li>Copies the source to the destination in a single operation. No extra copies required.</li> |
| </ol> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nd">@Test</span> |
| <span class="kd">public</span> <span class="kt">void</span> <span class="nf">copyOffHeapToMemoryMappedFile</span><span class="o">()</span> <span class="kd">throws</span> <span class="nc">Exception</span> <span class="o">{</span> |
| <span class="kt">long</span> <span class="n">bytes</span> <span class="o">=</span> <span class="mi">1L</span> <span class="o"><<</span> <span class="mi">32</span><span class="o">;</span> <span class="c1">//4GB</span> |
| <span class="kt">long</span> <span class="n">longs</span> <span class="o">=</span> <span class="n">bytes</span> <span class="o">>>></span> <span class="mi">3</span><span class="o">;</span> |
| |
| <span class="nc">File</span> <span class="n">file</span> <span class="o">=</span> <span class="k">new</span> <span class="nc">File</span><span class="o">(</span><span class="s">"TestFile.bin"</span><span class="o">);</span> |
| <span class="k">if</span> <span class="o">(</span><span class="n">file</span><span class="o">.</span><span class="na">exists</span><span class="o">())</span> <span class="o">{</span> <span class="n">file</span><span class="o">.</span><span class="na">delete</span><span class="o">();</span> <span class="o">}</span> |
| <span class="k">assert</span> <span class="n">file</span><span class="o">.</span><span class="na">createNewFile</span><span class="o">();</span> |
| <span class="k">assert</span> <span class="n">file</span><span class="o">.</span><span class="na">setWritable</span><span class="o">(</span><span class="kc">true</span><span class="o">,</span> <span class="kc">false</span><span class="o">);</span> |
| <span class="k">assert</span> <span class="n">file</span><span class="o">.</span><span class="na">isFile</span><span class="o">();</span> |
| <span class="n">file</span><span class="o">.</span><span class="na">deleteOnExit</span><span class="o">();</span> <span class="c1">//comment out if you want to examine the file.</span> |
| |
| <span class="k">try</span> <span class="o">(</span> |
| <span class="nc">WritableMapHandle</span> <span class="n">dstHandle</span> |
| <span class="o">=</span> <span class="nc">WritableMemory</span><span class="o">.</span><span class="na">writableMap</span><span class="o">(</span><span class="n">file</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="n">bytes</span><span class="o">,</span> <span class="nc">ByteOrder</span><span class="o">.</span><span class="na">nativeOrder</span><span class="o">());</span> |
| <span class="nc">WritableHandle</span> <span class="n">srcHandle</span> <span class="o">=</span> <span class="nc">WritableMemory</span><span class="o">.</span><span class="na">allocateDirect</span><span class="o">(</span><span class="n">bytes</span><span class="o">))</span> <span class="o">{</span> |
| |
| <span class="nc">WritableMemory</span> <span class="n">dstMem</span> <span class="o">=</span> <span class="n">dstHandle</span><span class="o">.</span><span class="na">getWritable</span><span class="o">();</span> |
| <span class="nc">WritableMemory</span> <span class="n">srcMem</span> <span class="o">=</span> <span class="n">srcHandle</span><span class="o">.</span><span class="na">getWritable</span><span class="o">();</span> |
| |
| <span class="k">for</span> <span class="o">(</span><span class="kt">long</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="o">(</span><span class="n">longs</span><span class="o">);</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> |
| <span class="n">srcMem</span><span class="o">.</span><span class="na">putLong</span><span class="o">(</span><span class="n">i</span> <span class="o"><<</span> <span class="mi">3</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span> <span class="c1">//load source with consecutive longs</span> |
| <span class="o">}</span> |
| |
| <span class="n">srcMem</span><span class="o">.</span><span class="na">copyTo</span><span class="o">(</span><span class="mi">0</span><span class="o">,</span> <span class="n">dstMem</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span> <span class="n">srcMem</span><span class="o">.</span><span class="na">getCapacity</span><span class="o">());</span> <span class="c1">//off-heap to off-heap copy</span> |
| |
| <span class="n">dstHandle</span><span class="o">.</span><span class="na">force</span><span class="o">();</span> <span class="c1">//push any remaining to the file</span> |
| |
| <span class="c1">//check end value</span> |
| <span class="n">assertEquals</span><span class="o">(</span><span class="n">dstMem</span><span class="o">.</span><span class="na">getLong</span><span class="o">((</span><span class="n">longs</span> <span class="o">-</span> <span class="mi">1L</span><span class="o">)</span> <span class="o"><<</span> <span class="mi">3</span><span class="o">),</span> <span class="n">longs</span> <span class="o">-</span> <span class="mi">1L</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| </code></pre></div></div> |
| |
| <h3 id="regions-and-writableregions">Regions and WritableRegions</h3> |
| <p>Similar to the <em>ByteBuffer slice()</em>, one can create a region or writable region, |
| which is a view into the same underlying resource.</p> |
| |
| <div class="language-java highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nd">@Test</span> |
| <span class="kd">public</span> <span class="kt">void</span> <span class="nf">checkRORegions</span><span class="o">()</span> <span class="o">{</span> |
| <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">16</span><span class="o">;</span> |
| <span class="kt">int</span> <span class="n">n2</span> <span class="o">=</span> <span class="n">n</span> <span class="o">/</span> <span class="mi">2</span><span class="o">;</span> |
| <span class="kt">long</span><span class="o">[]</span> <span class="n">arr</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">long</span><span class="o">[</span><span class="n">n</span><span class="o">];</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> <span class="n">arr</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">i</span><span class="o">;</span> <span class="o">}</span> |
| <span class="nc">Memory</span> <span class="n">mem</span> <span class="o">=</span> <span class="nc">Memory</span><span class="o">.</span><span class="na">wrap</span><span class="o">(</span><span class="n">arr</span><span class="o">);</span> |
| <span class="nc">Memory</span> <span class="n">reg</span> <span class="o">=</span> <span class="n">mem</span><span class="o">.</span><span class="na">region</span><span class="o">(</span><span class="n">n2</span> <span class="o">*</span> <span class="mi">8</span><span class="o">,</span> <span class="n">n2</span> <span class="o">*</span> <span class="mi">8</span><span class="o">);</span> |
| <span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n2</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span> |
| <span class="n">assertEquals</span><span class="o">(</span><span class="n">reg</span><span class="o">.</span><span class="na">getLong</span><span class="o">(</span><span class="n">i</span> <span class="o">*</span> <span class="mi">8</span><span class="o">),</span> <span class="n">i</span> <span class="o">+</span> <span class="n">n2</span><span class="o">);</span> |
| <span class="o">}</span> |
| <span class="o">}</span> |
| </code></pre></div></div> |
| |
| <h3 id="using-the-library">Using the Library</h3> |
| |
| <p>See the project <a href="https://github.com/apache/datasketches-memory/blob/master/README.md">README</a> for further instructions on how to use the Datasketches Memory library in your own applications.</p> |
| |
| </div> <!-- End content --> |
| </div> <!-- End row --> |
| </div> <!-- End Container --> |
| |
| <!-- Start _include/page_footer.html --> |
| <footer class="ds-footer"> |
| <div class="container"> |
| <div class="text-center"> |
| <p> |
| <div>Copyright © 2024 <a href="https://www.apache.org">Apache Software Foundation</a>, |
| Licensed under the Apache License, Version 2.0. All Rights Reserved. |
| | <a href="https://privacy.apache.org/policies/privacy-policy-public.html">Privacy Policy</a><br/> |
| Apache DataSketches, Apache, the Apache feather logo, and the Apache DataSketches project logos are trademarks of The Apache Software Foundation.<br/> |
| All other marks mentioned may be trademarks or registered trademarks of their respective owners. |
| </div> |
| </p> |
| </div> |
| </div> |
| </footer> |
| <!-- End _include/page_footer.html --> |
| |
| </body> |
| |
| </html> |
| <!-- End _layouts/doc_page.html--> |
