<jupyter_start><jupyter_text>Benchmark: Area computationBenchmark comparing area computation across:* [georust/geo](https://lib.rs/crates/geo) crate* The [geos C library](https://trac.osgeo.org/geos/), used through high-level Rust bindings via the [geos](https://lib.rs/crates/geos) crate Benchmarked operationEach iteration computes the area of the multi-polygon representing all districts of India a 100,000 times.  PrerequisitesGenerate data:```bashcd harnesscargo build --releaseLD_LIBRARY_PATH="${LD_LIBRARY_PATH}:/mnt/data/source/explore-georust/third_party/lib/geos/relwithdebinfo" target/release/benchmark_area --out-file ../analysis/benchmark_area/data.json --geojson-file ../data/india_districts/polbnda_ind.geojson --headlong --iterations 120```<jupyter_code>import os
data_absolute_path = os.path.join(os.getcwd(), 'data.json')
%run ../common/benchmark_analysis.ipynb
data_series = series_sans_outliers<jupyter_output>### Loading data from /mnt/data/source/explore-georust/analysis/benchmark_area/data.json
### Statistics: Raw data
                qps            
program         geo        geos
count    110.000000  110.000000
mean      10.231901    1.261647
std        0.261169    0.019653
min        8.507260    1.190689
25%       10.265279    1.257767
50%       10.298709    1.270308
75%       10.329201    1.274771
max       10.385171    1.278673<jupyter_text>Performance benchmarkingTo generate the following SVG:```bashcd harnesscargo build --releaseperf record -F 100 -g --call-graph dwarf -o ../analysis/benchmark_area/perf.data -- ./target/release/benchmark_area --geojson-file ../data/india_districts/polbnda_ind.geojson --out-file /dev/null --iterations 10 --headlong >/dev/nullcd ../analysis/benchmark_areaperf script -i perf.data | ../../third_party/stackcollapse-perf.pl > perf.collapsed-stacks.data../../third_party/flamegraph.pl perf.collapsed-stacks.data > perf.svg```![](./perf.svg)To dig in further, use```perf report -i perf.data --call-graph=fractal,0.5```Observations:* Over 61% of the time is spent inside `geos::algorithm::Area::ofRingSigned` in libgeos.so - geos area computation proper  * The descructor `geos::geom::CoordinateArraySequence::~CoordinateArraySequence` in the callgraph is a mystery* Over 29% of the time is spent inside `geo::algorithm::area::get_linestring_area` -- geo area computation* geos is *not* slow because of FFI.  It's the vectors!Vector iteration is 10x slower than Rust's iterators!![](./geo_area.png)![](./geos_area.png)  Uber-optimizedWhen building without debug info, gcc -O3 is used. This makes geos faster.```bashLD_LIBRARY_PATH="${LD_LIBRARY_PATH}:/mnt/data/source/explore-georust/third_party/lib/geos/release" target/release/benchmark_area --out-file ../analysis/benchmark_area/data-nodbg.json --geojson-file ../data/india_districts/polbnda_ind.geojson --headlong --iterations 120```<jupyter_code>import os
data_absolute_path = os.path.join(os.getcwd(), 'data-nodbg.json')
%run ../common/benchmark_analysis.ipynb<jupyter_output>### Loading data from /mnt/data/source/explore-georust/analysis/benchmark_area/data-nodbg.json
### Statistics: Raw data
                qps            
program         geo        geos
count    110.000000  110.000000
mean      10.212075    4.502662
std        0.378600    0.104565
min        7.341967    3.768708
25%       10.268325    4.513751
50%       10.304798    4.532483
75%       10.333955    4.547622
max       10.385256    4.569215<jupyter_text>Uber optimized geos - perf analysis.Generate with:```bashLD_LIBRARY_PATH="${LD_LIBRARY_PATH}:/mnt/data/source/explore-georust/third_party/lib/geos/release" perf record -F 300 -g --call-graph dwarf -o ../analysis/benchmark_area/perf-nodbg.data -- ./target/release/benchmark_area --geojson-file ../data/india_districts/polbnda_ind.geojson --out-file /dev/null --iterations 10 --headlong >/dev/null```Snippet from```bashperf report -i perf-nodbg.data --call-graph=fractal,0.5```![](./geos_area_still_iteration.png)Qualitatively unchanged. Less symbols, but largest time is still taken by the same iteration path  Root causeHistograms (with global timeshare shown):-    9.85%     0.22%  benchmark_area  benchmark_area  [.] benchmark_area::geo_area     9.63% benchmark_area::geo_area         as geo::algorithm::area::Area>::signed_area (inlined)        core::iter::traits::iterator::Iterator::fold (inlined)        _$LT$geo_types..multi_polygon..MultiPolygon$LT$T$GT$$u20$as$u20$geo..algorithm..area..Area$LT$T$GT$$GT$::signed_area::_$u7b$$u7b$closure$u7d$$u7d$::h7499759712fc2893 (inlined)         as geo::algorithm::area::Area>::signed_area (inlined)        geo::algorithm::area::get_linestring_area      - geo::algorithm::area::twice_signed_ring_area (inlined)         - 5.14%  as core::iter::traits::iterator::Iterator>::next (inlined)            - 2.95% core::option::Option::map (inlined)                 core::ops::function::impls:: for &mut F>::call_once (inlined)                 geo_types::line_string::LineString$LT$T$GT$::lines::_$u7b$$u7b$closure$u7d$$u7d$::h56776f40cf098343 (inlined)              2.19%  as core::iter::traits::iterator::Iterator>::next (inlined)         - 2.63% geo_types::line::Line::determinant (inlined)              ::sub (inlined)         - 1.86%  as geo::algorithm::map_coords::MapCoords>::map_coords (inlined)               as geo::algorithm::map_coords::MapCoords>::map_coords (inlined)              geo::algorithm::area::twice_signed_ring_area::_$u7b$$u7b$closure$u7d$$u7d$::hac06ea9fa53ccbc4 (inlined)              ::sub (inlined)-   78.45%     0.00%  benchmark_area  benchmark_area  [.] benchmark_area::geos_area     benchmark_area::geos_area     ::area     GEOSArea_r   - execute      - GEOSArea_r::{lambda()1}::operator()         - geos::geom::GeometryCollection::getArea            - 78.12% geos::geom::Polygon::getArea               - 77.46% geos::algorithm::Area::ofRing                  - 77.24% geos::algorithm::Area::ofRingSigned                     - 19.15% geos::geom::CoordinateArraySequence::getAt                          10.39% std::vector >::operator[]                          1.53% std::vector >::operator[]@plt               - 0.55% geos::geom::LineString::getCoordinatesRO                    std::unique_ptr >::get                    std::__uniq_ptr_impl >::_M_ptrThere are two large sources of the difference.77% of the time is spent inside geos::algorithm::Area::ofRingSigned. Of this,~20% is in a geos::geom::CoordinateArraySequence::getAt. So 50% is in calculationsare in geos::algorithm::Area::ofRingSignedMost of this time is spent in [calculation of the area proper](./geos::algorithm::Area::ofRingSigned.annotation):                     p2.x -= x0;  1.20         movsd  -0x80(%rbp),%xmm0  2.41         subsd  -0x20(%rbp),%xmm0 10.18         movsd  %xmm0,-0x80(%rbp)                     sum += p1.x * (p0.y - p2.y);  2.63         movsd  -0x60(%rbp),%xmm1               movsd  -0x38(%rbp),%xmm0               movsd  -0x78(%rbp),%xmm2               subsd  %xmm2,%xmm0  2.52         mulsd  %xmm1,%xmm0  6.46         movsd  -0x8(%rbp),%xmm1               addsd  %xmm1,%xmm0 11.71         movsd  %xmm0,-0x8(%rbp)Compared to this, benchmark_area::geo_area accounts for 9.63% of global timeshareOf this, core::iter::traits::iterator::Iterator>::next accounts for ~5%, so only~5% of the time is spent in [equivalent area computation as above](./geo::algorithm::area::get_linestring_area.annotation):              mulpd  %xmm2,%xmm4             _ZN45_$LT$f64$u20$as$u20$core..ops..arith..Sub$GT$3sub17h7b8b1be7ea3e7a7aE():  1.86         movapd %xmm4,%xmm2               unpckhpd %xmm4,%xmm2               subsd  %xmm2,%xmm4             _ZN45_$LT$f64$u20$as$u20$core..ops..arith..Add$GT$3add17hc97f37a33d9f3bdcE():               addsd  %xmm0,%xmm4             _ZN9geo_types11line_string19LineString$LT$T$GT$5lines28_$u7b$$u7b$closure$u7d$$u7d$17h56776f40cf098343E():  3.06         movupd (%rax),%xmm0             _ZN106_$LT$core..ops..range..Range$LT$usize$GT$$u20$as$u20$core..slice..index..SliceIndex$LT$$u5b$T$u5d$$GT$$GT$13get_unchecked17h00ddc2259fd66df5E():The key difference is the use of [movsd](https://c9x.me/x86/html/file_module_x86_id_204.html) instruction in geos (accounts for over 20% of total time) vs [movapd](https://c9x.me/x86/html/file_module_x86_id_179.html) and friends in geo.The Rust compiler successfully vectorizes the computations!The second source of difference is geos::geom::CoordinateArraySequence::getAt (20%) vs core::iter::traits::iterator::Iterator>::next (5%). Rust compiler is able to generatefar simpler machine code for iteration than C++ vectors.<jupyter_code>series_geo = data_series.iloc[:, 0]
assert series_geo.name == ('qps', 'geo')
series_geos = data_series.iloc[:, 1]
assert series_geos.name == ('qps', 'geos')

ratio = series_geo.divide(series_geos)

plt.style.use('dark_background')

@plt.rc_context({
    'figure.figsize': (12, 8),
    'font.size': 12,
    'image.cmap': plt.get_cmap('Pastel1'),
})
def initialize_plot():
    fig = plt.figure()
    return fig.add_subplot(title='area QPS ratio')

x = range(ratio.size)
ax = initialize_plot()
ax.plot(x, ratio, linewidth=0, marker='o', label='observed geo/geos QPS')
ax.plot(x, [ratio.mean()] * ratio.size, linewidth=1, label='mean geo/geos QPS')
ax.fill_between(x, ratio.mean() - ratio.std(), ratio.mean() + ratio.std(), alpha=0.2, color='white')
ax.legend()
ax.set_xlabel('observation')
ax.set_ylabel('queries per second ratio')
ax.grid(False)
plt.savefig('area_qps_ratio.svg', transparent=True)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14420555846879915, 'fraction_numerical': 0.06345044572627163, 'mean_word_length': 3.613449443638123, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 28, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '459534', 'license': 'Apache-2.0', 'n_tokens_mistral': 3707, 'n_tokens_neox': 3257, 'n_words': 621, 'path': 'analysis/benchmark_area/main.ipynb', 'repo_name': 'callpraths/explore-georust', 'size': '9535'}