diff options
-rw-r--r-- | doc/test/test_cow_darray_perf01.amd64.log | 350 | ||||
-rw-r--r-- | doc/test/test_cowvector_perf01.amd64.log | 153 | ||||
-rw-r--r-- | doc/test/test_cowvector_perf01.arm64-raspi4.log | 153 | ||||
-rw-r--r-- | doc/test/test_hashset_perf01.amd64.log | 117 | ||||
-rw-r--r-- | doc/test/test_hashset_perf01.arm64-raspi4.log | 117 | ||||
-rw-r--r-- | include/jau/counting_allocator.hpp | 7 | ||||
-rw-r--r-- | include/jau/cow_darray.hpp | 817 | ||||
-rw-r--r-- | include/jau/cow_iterator.hpp | 254 | ||||
-rw-r--r-- | include/jau/cow_vector.hpp | 238 | ||||
-rw-r--r-- | include/jau/darray.hpp | 821 | ||||
-rw-r--r-- | test/CMakeLists.txt | 3 | ||||
-rw-r--r-- | test/test_cow_darray_01.cpp | 380 | ||||
-rw-r--r-- | test/test_cow_darray_perf01.cpp | 565 | ||||
-rw-r--r-- | test/test_cowvector_perf01.cpp | 340 |
14 files changed, 3346 insertions, 969 deletions
diff --git a/doc/test/test_cow_darray_perf01.amd64.log b/doc/test/test_cow_darray_perf01.amd64.log new file mode 100644 index 0000000..69e64eb --- /dev/null +++ b/doc/test/test_cow_darray_perf01.amd64.log @@ -0,0 +1,350 @@ +COMMANDLINE scripts/test_cow_darray_perf01.sh -v normal +EXE_WRAPPER nice -20 +logbasename test_cow_darray_perf01.amd64 +logfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.0.log +valgrindlogfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.valgrind.0.log +callgrindoutfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.callgrind.0.out +nice -20 /usr/local/projects/zafena/jaulib/build-amd64/test/test_cow_darray_perf01 -v normal +argc 3, auto_run 0, perf_analysis 0 +Mem: stdvec_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio +Mem: stdvec_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio +Mem: stdvec_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio +Mem: darray_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 880 bytes, alloc[balance 1 = 9 - 8]], 1.100000 ratio +Mem: darray_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,304 bytes, alloc[balance 1 = 11 - 10]], 1.440000 ratio +Mem: darray_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 25,552 bytes, alloc[balance 1 = 16 - 15]], 1.597000 ratio +Mem: cowstdvec_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio +Mem: cowstdvec_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio +Mem: cowstdvec_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio +Mem: cowdarray_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 880 bytes, alloc[balance 1 = 1 - 0]], 1.100000 ratio +Mem: cowdarray_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,304 bytes, alloc[balance 1 = 1 - 0]], 1.440000 ratio +Mem: cowdarray_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 25,552 bytes, alloc[balance 1 = 1 - 0]], 1.597000 ratio + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +test_cow_darray_perf01 is a Catch v3.0.0-preview.3 host application. +Run with -? for options + +------------------------------------------------------------------------------- +Perf Test 01 - Fill Sequential and List, empty and reserve +------------------------------------------------------------------------------- +/test/test_cow_darray_perf01.cpp:504 +............................................................................... + +benchmark name samples iterations estimated + mean low mean high mean + std dev low std dev high std dev +------------------------------------------------------------------------------- +STD_Vector_empty_idx FillSeq_List +50 100 36 2.1168 ms + 587.887 ns 586.534 ns 592.851 ns + 11.6643 ns 2.59561 ns 26.681 ns + +STD_Vector_empty_idx FillSeq_List +100 100 21 2.1273 ms + 1.01551 us 1.01076 us 1.02473 us + 32.6187 ns 19.7948 ns 53.2098 ns + +STD_Vector_empty_idx FillSeq_List +1000 100 3 2.3295 ms + 7.7587 us 7.75414 us 7.77689 us + 42.9198 ns 4.0468 ns 101.951 ns + +STD_Vector_empty_itr FillSeq_List +50 100 36 2.1276 ms + 586.001 ns 585.784 ns 586.568 ns + 1.65525 ns 0.465353 ns 3.27567 ns + +STD_Vector_empty_itr FillSeq_List +100 100 21 2.0895 ms + 994.921 ns 988.919 ns 1.00582 us + 40.1812 ns 25.3082 ns 57.6708 ns + +STD_Vector_empty_itr FillSeq_List +1000 100 3 2.3886 ms + 7.87883 us 7.816 us 7.98781 us + 409.816 ns 278.711 ns 740.356 ns + +JAU_DArray_empty_idx FillSeq_List +50 100 35 2.114 ms + 598.635 ns 596.777 ns 605.661 ns + 16.3576 ns 3.66866 ns 38.0961 ns + +JAU_DArray_empty_idx FillSeq_List +100 100 19 2.1223 ms + 1.106 us 1.10402 us 1.1153 us + 18.5808 ns 0.490943 ns 44.1982 ns + +JAU_DArray_empty_idx FillSeq_List +1000 100 3 2.8092 ms + 9.3225 us 9.29807 us 9.38497 us + 184.594 ns 87.6997 ns 341.201 ns + +JAU_DArray_empty_itr FillSeq_List +50 100 36 2.142 ms + 596.304 ns 592.709 ns 604.02 ns + 25.6078 ns 13.9646 ns 44.649 ns + +JAU_DArray_empty_itr FillSeq_List +100 100 19 2.1546 ms + 1.1111 us 1.10853 us 1.11751 us + 18.3155 ns 2.03707 ns 34.3155 ns + +JAU_DArray_empty_itr FillSeq_List +1000 100 3 2.8344 ms + 9.30593 us 9.30037 us 9.33189 us + 52.9018 ns 3.95373 ns 125.894 ns + +COW_Vector_empty_itr FillSeq_List +50 100 4 2.3236 ms + 5.74342 us 5.69619 us 5.92492 us + 407.638 ns 103.644 ns 933.721 ns + +COW_Vector_empty_itr FillSeq_List +100 100 2 3.8364 ms + 19.5381 us 19.4755 us 19.6833 us + 470.471 ns 238.193 ns 793.648 ns + +COW_Vector_empty_itr FillSeq_List +1000 100 1 103.138 ms + 1.02219 ms 1.02134 ms 1.02303 ms + 4.30683 us 3.85196 us 4.88288 us + +COW_DArray_empty_itr FillSeq_List +50 100 12 2.1456 ms + 1.76765 us 1.76743 us 1.76851 us + 1.98944 ns 0.373864 ns 4.62752 ns + +COW_DArray_empty_itr FillSeq_List +100 100 7 2.2855 ms + 3.27837 us 3.26571 us 3.30378 us + 88.2901 ns 50.5299 ns 144.154 ns + +COW_DArray_empty_itr FillSeq_List +1000 100 1 2.8288 ms + 28.1568 us 28.1023 us 28.2788 us + 395.76 ns 197.003 ns 670.658 ns + +STD_Vector_rserv_itr FillSeq_List +50 100 41 2.1279 ms + 521.165 ns 519.728 ns 524.924 ns + 10.3168 ns 0.266432 ns 20.6426 ns + +STD_Vector_rserv_itr FillSeq_List +100 100 24 2.1096 ms + 880.622 ns 877.774 ns 886.438 ns + 19.8502 ns 10.6627 ns 31.7561 ns + +STD_Vector_rserv_itr FillSeq_List +1000 100 4 2.6292 ms + 6.58481 us 6.56973 us 6.63792 us + 124.657 ns 26.2394 ns 278.381 ns + +JAU_DArray_rserv_itr FillSeq_List +50 100 44 2.0944 ms + 504.908 ns 503.426 ns 508.953 ns + 10.9981 ns 0.347251 ns 23.449 ns + +JAU_DArray_rserv_itr FillSeq_List +100 100 26 2.1476 ms + 827.16 ns 825.085 ns 836.084 ns + 18.0184 ns 0.377244 ns 42.4347 ns + +JAU_DArray_rserv_itr FillSeq_List +1000 100 4 2.3976 ms + 6.00385 us 5.99214 us 6.06161 us + 115.24 ns 1.93334 ns 252.482 ns + +COW_Vector_rserv_itr FillSeq_List +50 100 4 2.476 ms + 6.12628 us 6.12033 us 6.15452 us + 57.0493 ns 3.45555 ns 135.858 ns + +COW_Vector_rserv_itr FillSeq_List +100 100 2 4.073 ms + 20.5219 us 20.4073 us 20.9229 us + 913.922 ns 52.6484 ns 2.0721 us + +COW_Vector_rserv_itr FillSeq_List +1000 100 1 108.419 ms + 1.08169 ms 1.08077 ms 1.08265 ms + 4.81349 us 4.35774 us 5.38341 us + +COW_Vector_rserv_itr FillSeq_List +50 100 4 2.4752 ms + 6.17815 us 6.1529 us 6.23063 us + 177.523 ns 102.004 ns 280.314 ns + +COW_Vector_rserv_itr FillSeq_List +100 100 2 4.0584 ms + 20.1429 us 20.0586 us 20.4957 us + 744.84 ns 137.805 ns 1.7365 us + +COW_Vector_rserv_itr FillSeq_List +1000 100 1 108.332 ms + 1.07729 ms 1.07656 ms 1.078 ms + 3.68093 us 3.21951 us 4.23509 us + + +------------------------------------------------------------------------------- +Perf Test 02 - Fill Unique and List, empty and reserve +------------------------------------------------------------------------------- +/test/test_cow_darray_perf01.cpp:530 +............................................................................... + +benchmark name samples iterations estimated + mean low mean high mean + std dev low std dev high std dev +------------------------------------------------------------------------------- +STD_Vector_empty_idx FillUni_List +50 100 11 2.0922 ms + 1.78899 us 1.78235 us 1.80339 us + 47.5893 ns 26.0812 ns 77.9321 ns + +STD_Vector_empty_idx FillUni_List +100 100 4 2.3412 ms + 6.24056 us 6.21462 us 6.30519 us + 196.305 ns 97.444 ns 407.914 ns + +STD_Vector_empty_idx FillUni_List +1000 100 1 39.3706 ms + 389.91 us 388.749 us 393.46 us + 9.43058 us 3.86633 us 20.7428 us + +STD_Vector_empty_itr FillUni_List +50 100 13 2.1619 ms + 1.62625 us 1.62237 us 1.636 us + 27.9497 ns 4.07125 ns 51.1131 ns + +STD_Vector_empty_itr FillUni_List +100 100 4 2.23 ms + 5.54929 us 5.54172 us 5.57753 us + 66.2521 ns 17.5609 ns 152.82 ns + +STD_Vector_empty_itr FillUni_List +1000 100 1 38.6387 ms + 387.279 us 386.262 us 391.178 us + 8.98648 us 2.04055 us 20.9355 us + +JAU_DArray_empty_idx FillUni_List +50 100 12 2.1828 ms + 1.88023 us 1.85714 us 1.90417 us + 119.67 ns 114.33 ns 135.271 ns + +JAU_DArray_empty_idx FillUni_List +100 100 4 2.7236 ms + 6.79534 us 6.77376 us 6.84645 us + 159.206 ns 78.086 ns 287.348 ns + +JAU_DArray_empty_idx FillUni_List +1000 100 1 38.8248 ms + 394.747 us 394.236 us 395.342 us + 2.81011 us 2.40999 us 3.27223 us + +JAU_DArray_empty_itr FillUni_List +50 100 13 2.1112 ms + 1.6465 us 1.64008 us 1.66125 us + 48.7547 ns 27.7939 ns 77.669 ns + +JAU_DArray_empty_itr FillUni_List +100 100 4 2.5492 ms + 6.36098 us 6.34687 us 6.37031 us + 57.031 ns 42.8585 ns 112.034 ns + +JAU_DArray_empty_itr FillUni_List +1000 100 1 39.8971 ms + 399.012 us 393.175 us 407.601 us + 35.6943 us 26.9714 us 44.1455 us + +COW_Vector_empty_itr FillUni_List +50 100 2 2.4302 ms + 12.219 us 12.1941 us 12.2724 us + 177.965 ns 73.8311 ns 305.141 ns + +COW_Vector_empty_itr FillUni_List +100 100 1 3.6369 ms + 36.292 us 36.2068 us 36.5079 us + 643.556 ns 285.442 ns 1.27906 us + +COW_Vector_empty_itr FillUni_List +1000 100 1 182.543 ms + 1.8947 ms 1.8934 ms 1.89613 ms + 6.92523 us 6.21527 us 7.78582 us + +COW_DArray_empty_itr FillUni_List +50 100 3 2.1018 ms + 6.99721 us 6.9725 us 7.04634 us + 169.177 ns 95.3738 ns 262.178 ns + +COW_DArray_empty_itr FillUni_List +100 100 2 3.3468 ms + 16.7829 us 16.714 us 16.9106 us + 464.357 ns 281.39 ns 699.268 ns + +COW_DArray_empty_itr FillUni_List +1000 100 1 60.1642 ms + 593.482 us 592.789 us 594.21 us + 3.64366 us 3.11135 us 4.36028 us + +STD_Vector_rserv_itr FillUni_List +50 100 14 2.1126 ms + 1.5431 us 1.53312 us 1.56815 us + 70.7362 ns 4.62231 ns 130.265 ns + +STD_Vector_rserv_itr FillUni_List +100 100 4 2.1356 ms + 5.42934 us 5.40332 us 5.48336 us + 182.126 ns 105.133 ns 322.296 ns + +STD_Vector_rserv_itr FillUni_List +1000 100 1 37.5587 ms + 371.987 us 371.528 us 372.643 us + 2.76657 us 2.13462 us 4.02853 us + +JAU_DArray_rserv_itr FillUni_List +50 100 13 2.0904 ms + 1.6157 us 1.61182 us 1.6312 us + 33.6739 ns 3.69632 ns 78.0574 ns + +JAU_DArray_rserv_itr FillUni_List +100 100 4 2.2192 ms + 5.33926 us 5.33073 us 5.3557 us + 58.2143 ns 30.7842 ns 104.499 ns + +JAU_DArray_rserv_itr FillUni_List +1000 100 1 37.1666 ms + 370.967 us 370.349 us 372.018 us + 4.03079 us 2.70746 us 6.23372 us + +COW_Vector_rserv_itr FillUni_List +50 100 2 2.4072 ms + 11.9813 us 11.89 us 12.2839 us + 708.205 ns 35.07 ns 1.58406 us + +COW_Vector_rserv_itr FillUni_List +100 100 1 3.5566 ms + 35.4723 us 35.3395 us 35.725 us + 905.511 ns 543.264 ns 1.4284 us + +COW_Vector_rserv_itr FillUni_List +1000 100 1 180.037 ms + 1.80119 ms 1.79948 ms 1.80266 ms + 8.06882 us 6.80229 us 9.89432 us + +COW_DArray_rserv_itr FillUni_List +50 100 4 2.5848 ms + 6.46866 us 6.467 us 6.47635 us + 15.577 ns 1.36692 ns 37.0103 ns + +COW_DArray_rserv_itr FillUni_List +100 100 2 3.1924 ms + 15.8892 us 15.8474 us 16.0002 us + 328.232 ns 139.156 ns 660.64 ns + +COW_DArray_rserv_itr FillUni_List +1000 100 1 57.9012 ms + 573.339 us 572.701 us 574.159 us + 3.65916 us 2.96615 us 4.6329 us + + +=============================================================================== +All tests passed (64672560 assertions in 3 test cases) + diff --git a/doc/test/test_cowvector_perf01.amd64.log b/doc/test/test_cowvector_perf01.amd64.log deleted file mode 100644 index 1c07f45..0000000 --- a/doc/test/test_cowvector_perf01.amd64.log +++ /dev/null @@ -1,153 +0,0 @@ -argc 3, auto-run 0 -Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -test_cowvector_perf01 is a Catch v3.0.0-preview.3 host application. -Run with -? for options - -------------------------------------------------------------------------------- -STD Vector Perf Test 01 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:231 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 60 2.082 ms - 350.144 ns 349.585 ns 351.737 ns - 4.42199 ns 2.00301 ns 9.59688 ns - -Seq_List 50 100 38 2.0672 ms - 541.848 ns 541.807 ns 541.982 ns - 0.345592 ns 0.122757 ns 0.771527 ns - -Seq_List 100 100 23 2.116 ms - 920.523 ns 916.727 ns 927.621 ns - 25.7041 ns 15.8618 ns 38.9443 ns - -Seq_List 200 100 13 2.1879 ms - 1.72219 us 1.71326 us 1.73803 us - 58.9475 ns 36.6068 ns 87.466 ns - -Seq_List 1000 100 3 2.1756 ms - 7.32046 us 7.28011 us 7.40319 us - 283.239 ns 160.691 ns 468.914 ns - - -Mem: cowvec_11 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio -Mem: cowvec_11 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio -Mem: cowvec_11 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio -Mem: cowvec_11 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio -Mem: cowvec_11 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio -------------------------------------------------------------------------------- -COW Vector Perf Test 11 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:258 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 10 2.284 ms - 2.27211 us 2.26364 us 2.28704 us - 55.6548 ns 36.1072 ns 83.1873 ns - -Seq_List 50 100 4 2.4708 ms - 6.14203 us 6.12294 us 6.19001 us - 138.624 ns 22.5121 ns 254.346 ns - -Seq_List 100 100 1 2.0615 ms - 20.2991 us 20.2313 us 20.4742 us - 502.929 ns 120.184 ns 907.942 ns - -Seq_List 200 100 1 6.3719 ms - 63.9441 us 63.7343 us 64.293 us - 1.34563 us 895.153 ns 2.00555 us - -Seq_List 1000 100 1 106.105 ms - 1.04617 ms 1.04518 ms 1.04712 ms - 4.92832 us 4.12439 us 6.22148 us - - -Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio -------------------------------------------------------------------------------- -STD Vector Perf Test 02 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:286 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 24 2.0616 ms - 846.189 ns 843.472 ns 852.225 ns - 19.5557 ns 9.92097 ns 34.0883 ns - -Unique Find 50 100 9 2.0943 ms - 2.27419 us 2.27358 us 2.2756 us - 4.66728 ns 2.60139 ns 7.45502 ns - -Unique Find 100 100 3 2.2263 ms - 7.79227 us 7.75814 us 7.84904 us - 221.114 ns 150.556 ns 325.101 ns - -Unique Find 200 100 1 2.9961 ms - 29.4696 us 29.2017 us 29.7451 us - 1.3753 us 964.726 ns 2.04338 us - -Unique Find 1000 100 1 101.375 ms - 1.00886 ms 1.00591 ms 1.01206 ms - 15.7557 us 13.6415 us 20.1276 us - - -Mem: cowvec_12 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio -Mem: cowvec_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio -Mem: cowvec_12 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio -Mem: cowvec_12 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio -Mem: cowvec_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio -------------------------------------------------------------------------------- -COW Vector Perf Test 12 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:313 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 5 2.2945 ms - 4.6223 us 4.61348 us 4.63931 us - 60.3974 ns 38.3079 ns 116.061 ns - -Unique Find 50 100 2 3.169 ms - 15.8017 us 15.7506 us 15.9111 us - 365.232 ns 205.942 ns 667.899 ns - -Unique Find 100 100 1 5.8658 ms - 57.5863 us 57.486 us 57.9267 us - 839.216 ns 279.156 ns 1.87942 us - -Unique Find 200 100 1 21.1047 ms - 210.697 us 210.437 us 211.044 us - 1.52385 us 1.22872 us 2.03313 us - -Unique Find 1000 100 1 467.482 ms - 4.69308 ms 4.6879 ms 4.69895 ms - 28.3154 us 25.1022 us 32.3612 us - - -=============================================================================== -All tests passed (17403632 assertions in 4 test cases) - diff --git a/doc/test/test_cowvector_perf01.arm64-raspi4.log b/doc/test/test_cowvector_perf01.arm64-raspi4.log deleted file mode 100644 index 7497ffe..0000000 --- a/doc/test/test_cowvector_perf01.arm64-raspi4.log +++ /dev/null @@ -1,153 +0,0 @@ -argc 3, auto-run 0 -Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -test_cowvector_perf01 is a Catch v3.0.0-preview.3 host application. -Run with -? for options - -------------------------------------------------------------------------------- -STD Vector Perf Test 01 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:231 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 77 9.9099 ms - 1.27432 us 1.27211 us 1.27914 us - 15.8552 ns 6.72908 ns 27.0865 ns - -Seq_List 50 100 55 9.9 ms - 1.79602 us 1.78413 us 1.84783 us - 107.523 ns 14.5073 ns 253.156 ns - -Seq_List 100 100 34 9.9518 ms - 2.9136 us 2.90828 us 2.92575 us - 39.7364 ns 22.7895 ns 64.0512 ns - -Seq_List 200 100 21 10.0926 ms - 4.77759 us 4.77012 us 4.79622 us - 54.9702 ns 16.1965 ns 97.5445 ns - -Seq_List 1000 100 6 11.5296 ms - 19.1583 us 19.1215 us 19.2311 us - 254.646 ns 157.209 ns 395.481 ns - - -Mem: cowvec_11 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio -Mem: cowvec_11 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio -Mem: cowvec_11 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio -Mem: cowvec_11 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio -Mem: cowvec_11 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio -------------------------------------------------------------------------------- -COW Vector Perf Test 11 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:258 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 8 10.5888 ms - 13.4481 us 13.4223 us 13.4991 us - 178.586 ns 109.07 ns 277.353 ns - -Seq_List 50 100 3 10.1469 ms - 34.5996 us 34.5337 us 34.748 us - 482.345 ns 282.181 ns 759.841 ns - -Seq_List 100 100 2 18.8188 ms - 94.4849 us 94.3041 us 94.8347 us - 1.23247 us 752.838 ns 1.9215 us - -Seq_List 200 100 1 26.7126 ms - 266.465 us 266.108 us 267.02 us - 2.23473 us 1.57151 us 2.96187 us - -Seq_List 1000 100 1 445.089 ms - 4.43661 ms 4.43537 ms 4.43874 ms - 8.07672 us 5.41298 us 14.4825 us - - -Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio -------------------------------------------------------------------------------- -STD Vector Perf Test 02 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:286 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 26 9.9866 ms - 3.83536 us 3.82892 us 3.85186 us - 47.3465 ns 10.36 ns 85.6373 ns - -Unique Find 50 100 11 10.219 ms - 9.31415 us 9.294 us 9.35288 us - 136.606 ns 76.0691 ns 204.992 ns - -Unique Find 100 100 4 11.1196 ms - 27.9158 us 27.8657 us 28.0241 us - 361.204 ns 203.807 ns 581.343 ns - -Unique Find 200 100 2 18.9416 ms - 94.8942 us 94.7546 us 95.1397 us - 923.567 ns 584.085 ns 1.32101 us - -Unique Find 1000 100 1 364.572 ms - 3.64712 ms 3.64621 ms 3.64952 ms - 7.03117 us 3.22424 us 14.8312 us - - -Mem: cowvec_12 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio -Mem: cowvec_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio -Mem: cowvec_12 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio -Mem: cowvec_12 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio -Mem: cowvec_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio -------------------------------------------------------------------------------- -COW Vector Perf Test 12 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_cowvector_perf01.cpp:313 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 3 10.5069 ms - 34.8512 us 34.7742 us 35.0189 us - 551.761 ns 294.3 ns 931.225 ns - -Unique Find 50 100 1 11.7274 ms - 116.652 us 116.491 us 117.052 us - 1.1968 us 348.796 ns 2.12363 us - -Unique Find 100 100 1 42.362 ms - 420.924 us 420.491 us 421.544 us - 2.60965 us 1.95353 us 3.25359 us - -Unique Find 200 100 1 156.78 ms - 1.5621 ms 1.56129 ms 1.56296 ms - 4.24603 us 3.94813 us 4.6176 us - -Unique Find 1000 100 1 3.48784 s - 34.8407 ms 34.837 ms 34.8487 ms - 26.8157 us 15.8642 us 52.1366 us - - -=============================================================================== -All tests passed (4953760 assertions in 4 test cases) - diff --git a/doc/test/test_hashset_perf01.amd64.log b/doc/test/test_hashset_perf01.amd64.log deleted file mode 100644 index ac70875..0000000 --- a/doc/test/test_hashset_perf01.amd64.log +++ /dev/null @@ -1,117 +0,0 @@ -argc 3, auto-run 0 -Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -test_hashset_perf01 is a Catch v3.0.0-preview.3 host application. -Run with -? for options - -------------------------------------------------------------------------------- -STD Vector Perf Test 01 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:269 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 60 2.064 ms - 343.05 ns 342.936 ns 343.582 ns - 1.07506 ns 0.0932254 ns 2.55378 ns - -Seq_List 50 100 39 2.067 ms - 550.599 ns 546.832 ns 556.485 ns - 23.629 ns 16.807 ns 38.1638 ns - -Seq_List 100 100 23 2.1344 ms - 908.328 ns 905.844 ns 915.301 ns - 18.916 ns 2.60158 ns 39.6416 ns - -Seq_List 200 100 13 2.1619 ms - 1.6673 us 1.66284 us 1.67519 us - 29.6194 ns 19.2921 ns 47.6946 ns - -Seq_List 1000 100 3 2.1549 ms - 7.34832 us 7.30432 us 7.43755 us - 306.073 ns 179.633 ns 483.433 ns - - -Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio -------------------------------------------------------------------------------- -STD Vector Perf Test 02 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:297 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 24 2.0472 ms - 852.497 ns 849.73 ns 858.158 ns - 19.3529 ns 10.6049 ns 30.5871 ns - -Unique Find 50 100 9 2.0709 ms - 2.24281 us 2.22486 us 2.25011 us - 53.3331 ns 15.7256 ns 94.6539 ns - -Unique Find 100 100 3 2.2842 ms - 6.75987 us 6.7288 us 6.81588 us - 206.88 ns 129.222 ns 302.069 ns - -Unique Find 200 100 1 2.7023 ms - 26.4917 us 26.4056 us 26.6488 us - 572.088 ns 274.826 ns 957.771 ns - -Unique Find 1000 100 1 84.9358 ms - 970.189 us 968.48 us 972.371 us - 9.84229 us 7.6143 us 14.9796 us - - -Mem: stdset_12 (full_): Elements 25 x 16 bytes; CAlloc[ 600 bytes, alloc[balance 25 = 25 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,200 bytes, alloc[balance 50 = 50 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 100 x 16 bytes; CAlloc[ 2,400 bytes, alloc[balance 100 = 100 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 200 x 16 bytes; CAlloc[ 4,800 bytes, alloc[balance 200 = 200 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 24,000 bytes, alloc[balance 1,000 = 1,000 - 0]], 1.500000 ratio -------------------------------------------------------------------------------- -STD Unordered-Set Perf Test 12 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:324 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 12 2.1552 ms - 1.81641 us 1.8122 us 1.83224 us - 36.556 ns 7.89957 ns 84.0457 ns - -Unique Find 50 100 7 2.359 ms - 3.3691 us 3.36238 us 3.39531 us - 57.3478 ns 6.25338 ns 131.391 ns - -Unique Find 100 100 4 2.6164 ms - 6.49391 us 6.48824 us 6.51029 us - 45.1634 ns 19.76 ns 97.6575 ns - -Unique Find 200 100 2 2.764 ms - 13.3148 us 13.2758 us 13.4136 us - 294.994 ns 142.841 ns 589.103 ns - -Unique Find 1000 100 1 8.7068 ms - 86.4785 us 86.267 us 86.9334 us - 1.50441 us 802.647 ns 2.52316 us - - -=============================================================================== -All tests passed (17601392 assertions in 3 test cases) - diff --git a/doc/test/test_hashset_perf01.arm64-raspi4.log b/doc/test/test_hashset_perf01.arm64-raspi4.log deleted file mode 100644 index a362fa1..0000000 --- a/doc/test/test_hashset_perf01.arm64-raspi4.log +++ /dev/null @@ -1,117 +0,0 @@ -argc 3, auto-run 0 -Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -test_hashset_perf01 is a Catch v3.0.0-preview.3 host application. -Run with -? for options - -------------------------------------------------------------------------------- -STD Vector Perf Test 01 - Fill Sequential and List -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:269 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Seq_List 25 100 78 10.101 ms - 1.29545 us 1.2927 us 1.3001 us - 17.8456 ns 12.1376 ns 26.3005 ns - -Seq_List 50 100 55 10.197 ms - 1.84654 us 1.84393 us 1.85299 us - 19.4339 ns 6.01208 ns 34.476 ns - -Seq_List 100 100 35 10.1465 ms - 2.90007 us 2.89447 us 2.9121 us - 40.0101 ns 23.2939 ns 62.6749 ns - -Seq_List 200 100 21 10.0674 ms - 4.79983 us 4.78373 us 4.8477 us - 129.534 ns 47.2952 ns 274.068 ns - -Seq_List 1000 100 6 11.4552 ms - 19.1848 us 19.1531 us 19.261 us - 246.522 ns 143.048 ns 391.5 ns - - -Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio -Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio -------------------------------------------------------------------------------- -STD Vector Perf Test 02 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:297 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 27 10.1493 ms - 3.79413 us 3.78826 us 3.8091 us - 43.2259 ns 11.7687 ns 77.1456 ns - -Unique Find 50 100 11 10.0749 ms - 9.21581 us 9.19898 us 9.25444 us - 125.095 ns 72.4751 ns 198.256 ns - -Unique Find 100 100 4 10.9788 ms - 27.6046 us 27.5425 us 27.7244 us - 412.409 ns 217.397 ns 623.793 ns - -Unique Find 200 100 2 18.8014 ms - 94.2517 us 94.1176 us 94.4959 us - 894.732 ns 565.305 ns 1.28047 us - -Unique Find 1000 100 1 343.853 ms - 3.43966 ms 3.43877 ms 3.44153 ms - 6.31207 us 3.50588 us 12.5288 us - - -Mem: stdset_12 (full_): Elements 25 x 16 bytes; CAlloc[ 600 bytes, alloc[balance 25 = 25 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,200 bytes, alloc[balance 50 = 50 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 100 x 16 bytes; CAlloc[ 2,400 bytes, alloc[balance 100 = 100 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 200 x 16 bytes; CAlloc[ 4,800 bytes, alloc[balance 200 = 200 - 0]], 1.500000 ratio -Mem: stdset_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 24,000 bytes, alloc[balance 1,000 = 1,000 - 0]], 1.500000 ratio -------------------------------------------------------------------------------- -STD Unordered-Set Perf Test 12 - Fill Unique and Find-Each -------------------------------------------------------------------------------- -/test/test_hashset_perf01.cpp:324 -............................................................................... - -benchmark name samples iterations estimated - mean low mean high mean - std dev low std dev high std dev -------------------------------------------------------------------------------- -Unique Find 25 100 14 10.4202 ms - 7.47964 us 7.46322 us 7.51494 us - 118.007 ns 69.3892 ns 186.392 ns - -Unique Find 50 100 8 10.6464 ms - 13.284 us 13.248 us 13.3487 us - 239.185 ns 152.993 ns 359.936 ns - -Unique Find 100 100 4 10.7904 ms - 27.1248 us 27.0621 us 27.2544 us - 441.752 ns 252.981 ns 695.429 ns - -Unique Find 200 100 2 11.4072 ms - 57.1536 us 56.7599 us 58.7903 us - 3.51188 us 669.03 ns 8.19054 us - -Unique Find 1000 100 1 33.7565 ms - 338.059 us 337.468 us 338.85 us - 3.47204 us 2.71059 us 4.28299 us - - -=============================================================================== -All tests passed (5198408 assertions in 3 test cases) - diff --git a/include/jau/counting_allocator.hpp b/include/jau/counting_allocator.hpp index 5ec5ced..3cada17 100644 --- a/include/jau/counting_allocator.hpp +++ b/include/jau/counting_allocator.hpp @@ -33,6 +33,13 @@ namespace jau { +/** + * Performance counter std::allocator specialization. + * <p> + * Not overriding deprecated (C++17) and removed (C++20) + * methods: address(), max_size(), construct() and destroy(). + * </p> + */ template <class T> struct counting_allocator : public std::allocator<T> { diff --git a/include/jau/cow_darray.hpp b/include/jau/cow_darray.hpp new file mode 100644 index 0000000..cfcae18 --- /dev/null +++ b/include/jau/cow_darray.hpp @@ -0,0 +1,817 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright (c) 2020 Gothel Software e.K. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef JAU_COW_DARRAY_HPP_ +#define JAU_COW_DARRAY_HPP_ + +#include <cstring> +#include <string> +#include <cstdint> +#include <atomic> +#include <memory> +#include <mutex> +#include <condition_variable> +#include <algorithm> + +#include <jau/debug.hpp> +#include <jau/darray.hpp> +#include <jau/basic_types.hpp> +#include <jau/ordered_atomic.hpp> +#include <jau/cow_iterator.hpp> + +namespace jau { + + /** + * Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage, + * exposing <i>lock-free</i> read operations using SC-DRF atomic synchronization. + * <p> + * The store is owned using a shared reference to the data structure, + * allowing its replacement on Copy-On-Write (CoW). + * </p> + * <p> + * Writing to the store utilizes a mutex lock to avoid data races + * on the instances' write operations only, leaving read operations <i>lock-free</i>.<br> + * Write operations replace the store reference with a new instance using + * jau::sc_atomic_critical to synchronize with read operations. + * </p> + * <p> + * Reading from the store is <i>lock-free</i> and accesses the store reference using + * jau::sc_atomic_critical to synchronizing with write operations. + * </p> + * <p> + * Immutable storage const_iterators are supported via jau::cow_ro_iterator, + * which are constructed <i>lock-free</i>.<br> + * jau::cow_ro_iterator hold a snapshot retrieved via jau::cow_darray::get_snapshot() + * until its destruction. + * </p> + * <p> + * Mutable storage iterators are supported via jau::cow_rw_iterator, + * which are constructed holding the write-lock.<br> + * jau::cow_rw_iterator hold a new store copy via jau::cow_darray::copy_store(), + * which replaces the current store via jau::cow_darray::set_store() at destruction. + * </p> + * <p> + * Both, jau::cow_ro_iterator and jau::cor_rw_iterator are harmonized + * to work with jau::darray::const_iterator and jau::darray::iterator + * for all iterator based operations. + * </p> + * <p> + * Index operation via ::operator[](size_t) or ::at(size_t) are not supported for now, + * since they would be only valid if Value_type itself is a std::shared_ptr + * and hence prohibit the destruction of the object if mutating the storage, + * e.g. via jau::cow_darray::push_back(). + * </p> + * <p> + * Custom mutable write operations are also supported via + * jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() and jau::cow_darray::set_store().<br> + * See example in jau::cow_darray::set_store() + * </p> + * + * </p> + * See also: + * <pre> + * - Sequentially Consistent (SC) ordering or SC-DRF (data race free) <https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering> + * - std::memory_order <https://en.cppreference.com/w/cpp/atomic/memory_order> + * </pre> + */ + template <typename Value_type, typename Alloc_type = std::allocator<Value_type>, typename Size_type = jau::nsize_t> + class cow_darray + { + public: + typedef darray<Value_type, Alloc_type, Size_type> storage_t; + typedef std::shared_ptr<storage_t> storage_ref_t; + + /** + * Immutable, read-only const_iterator, lock-free, + * holding the current shared store reference until destruction. + * <p> + * Using jau::cow_darray::get_snapshot() at construction. + * </p> + */ + typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator; + + /** + * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. + * <p> + * Using jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() at construction<br> + * and jau::cow_darray::set_store() at destruction. + * </p> + */ + typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_darray> iterator; + + /** Default growth factor using the golden ratio 1.618 */ + inline static const float DEFAULT_GROWTH_FACTOR = 1.618f; + + private: + storage_ref_t store_ref; + sc_atomic_bool sync_atomic; + std::recursive_mutex mtx_write; + + public: + // ctor w/o elements + + /** + * Default constructor, giving almost zero capacity and zero memory footprint, but the shared empty jau::darray + */ + constexpr cow_darray() noexcept + : store_ref(std::make_shared<storage_t>()), sync_atomic(false) {} + + /** + * Creating an empty instance with initial capacity and other (default) properties. + * @param capacity initial capacity of the new instance. + * @param growth_factor given growth factor + * @param alloc given Alloc_type + */ + constexpr explicit cow_darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : store_ref(std::make_shared<storage_t>(capacity, growth_factor, alloc)), sync_atomic(false) {} + + // conversion ctor on storage_t elements + + constexpr cow_darray(const storage_t& x) + : store_ref(std::make_shared<storage_t>(x)), sync_atomic(false) {} + + constexpr explicit cow_darray(const storage_t& x, const float growth_factor, const Alloc_type& alloc) + : store_ref(std::make_shared<storage_t>(x, growth_factor, alloc)), sync_atomic(false) {} + + constexpr cow_darray(storage_t && x) noexcept + : store_ref(std::make_shared<storage_t>(std::move(x))), sync_atomic(false) {} + + constexpr explicit cow_darray(storage_t && x, const float growth_factor, const Alloc_type& alloc) noexcept + : store_ref(std::make_shared<storage_t>(std::move(x), growth_factor, alloc)), sync_atomic(false) {} + + // copy_ctor on cow_darray elements + + /** + * Creates a new instance, copying all elements from the given array.<br> + * Capacity and size will equal the given array, i.e. the result is a trimmed array. + * @param x the given cow_darray, all elements will be copied into the new instance. + */ + constexpr cow_darray(const cow_darray& x) + : sync_atomic(false) { + storage_ref_t x_store_ref; + { + sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic ); + x_store_ref = x.store_ref; + } + store_ref = std::make_shared<storage_t>( *x_store_ref ); + } + + /** + * Creates a new instance, copying all elements from the given array.<br> + * Capacity and size will equal the given array, i.e. the result is a trimmed array. + * @param x the given cow_darray, all elements will be copied into the new instance. + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr explicit cow_darray(const cow_darray& x, const float growth_factor, const Alloc_type& alloc) + : sync_atomic(false) { + storage_ref_t x_store_ref; + { + sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic ); + x_store_ref = x.store_ref; + } + store_ref = std::make_shared<storage_t>( *x_store_ref, growth_factor, alloc ); + } + + /** + * Creates a new instance with custom initial storage capacity, copying all elements from the given array.<br> + * Size will equal the given array. + * <p> + * Calculated safe capacity is: <code>std::max<Size_type>(x.size(), _capacity)</code> + * </p> + * @param x the given cow_darray, all elements will be copied into the new instance. + * @param _capacity custom initial storage capacity + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr explicit cow_darray(const cow_darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc) + : sync_atomic(false) { + storage_ref_t x_store_ref; + { + sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic ); + x_store_ref = x.store_ref; + } + store_ref = std::make_shared<storage_t>( *x_store_ref, _capacity, growth_factor, alloc ); + } + + // move_ctor on cow_darray elements + + constexpr cow_darray(cow_darray && x) noexcept { + // swap store_ref + store_ref = std::move(x.store_ref); + x.store_ref = nullptr; + // not really necessary + sync_atomic = std::move(x.sync_atomic); + } + + // ctor on const_iterator and foreign template iterator + + /** + * Creates a new instance with custom initial storage capacity, + * copying all elements from the given const_iterator Value_type range [first, last).<br> + * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>. + * <p> + * Calculated safe capacity is: <code>std::max<Size_type>(Size_type(last-first), _capacity)</code> + * </p> + * @param _capacity custom initial storage capacity + * @param first const_iterator to first element of Value_type range [first, last) + * @param last const_iterator to last element of Value_type range [first, last) + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr cow_darray(const Size_type _capacity, const_iterator first, const_iterator last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : store_ref(std::make_shared<storage_t>(_capacity, first.underling(), last.underling(), growth_factor, alloc)), sync_atomic(false) + { } + + /** + * Creates a new instance with custom initial storage capacity, + * copying all elements from the given template input-iterator Value_type range [first, last).<br> + * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>. + * <p> + * Calculated safe capacity is: <code>std::max<Size_type>(Size_type(last-first), _capacity)</code> + * </p> + * @tparam InputIt template input-iterator custom type + * @param _capacity custom initial storage capacity + * @param first template input-iterator to first element of Value_type range [first, last) + * @param last template input-iterator to last element of Value_type range [first, last) + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + template< class InputIt > + constexpr explicit cow_darray(const Size_type _capacity, InputIt first, InputIt last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : store_ref(std::make_shared<storage_t>(_capacity, first, last, growth_factor, alloc)), sync_atomic(false) + { } + + + ~cow_darray() noexcept { } + + // cow_vector features + + /** + * Returns this instances' recursive write mutex, allowing user to + * implement more complex mutable write operations. + * <p> + * See example in jau::cow_darray::set_store() + * </p> + * + * @see jau::cow_darray::get_write_mutex() + * @see jau::cow_darray::copy_store() + * @see jau::cow_darray::set_store() + */ + constexpr std::recursive_mutex & get_write_mutex() noexcept { return mtx_write; } + + /** + * Returns a new shared_ptr copy of the underlying store, + * i.e. using a new copy-constructed vectore. + * <p> + * See example in jau::cow_darray::set_store() + * </p> + * <p> + * This special operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * @see jau::cow_darray::get_write_mutex() + * @see jau::cow_darray::copy_store() + * @see jau::cow_darray::set_store() + */ + storage_ref_t copy_store() { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + return std::make_shared<storage_t>( *store_ref ); + } + + /** + * Special case facility allowing the user to replace the current store + * with the given value, potentially acquired via jau::cow_darray::copy_store() + * and mutated while holding the jau::cow_darray::get_write_mutex() lock. + * <p> + * This is a move operation, i.e. the given new_store_ref is invalid on the caller side + * after this operation. <br> + * User shall pass the store via std::move() + * <pre> + * cow_darray<std::shared_ptr<Thing>> list; + * ... + * { + * const std::lock_guard<std::recursive_mutex> lock(list.get_write_mutex()); + * std::shared_ptr<std::vector<std::shared_ptr<Thing>>> snapshot = list.copy_store(); + * ... + * some fancy mutation + * ... + * list.set_store(std::move(snapshot)); + * } + * </pre> + * </p> + * @param new_store_ref the user store to be moved here, replacing the current store. + * + * @see jau::cow_darray::get_write_mutex() + * @see jau::cow_darray::copy_store() + * @see jau::cow_darray::set_store() + */ + constexpr void set_store(storage_ref_t && new_store_ref) noexcept { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + sc_atomic_critical sync(sync_atomic); + store_ref = std::move( new_store_ref ); + } + + /** + * Returns the current snapshot of the underlying shared std::vector<T> reference. + * <p> + * Note that this snapshot will be outdated by the next (concurrent) write operation.<br> + * The returned referenced vector is still valid and not mutated, + * but does not represent the current content of this cow_darray instance. + * </p> + * <p> + * This read operation is <i>lock-free</i>. + * </p> + * @see jau::for_each_cow + */ + constexpr storage_ref_t get_snapshot() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref; + } + + // const_iterator, non mutable, read-only + + constexpr const_iterator begin() const noexcept { + return const_iterator(get_snapshot(), store_ref->cbegin()); + } + + constexpr const_iterator cbegin() const noexcept { + return const_iterator(get_snapshot(), store_ref->cbegin()); + } + + constexpr const_iterator end() const noexcept { + return const_iterator(get_snapshot(), store_ref->cend()); + } + + constexpr const_iterator cend() const noexcept { + return const_iterator(get_snapshot(), store_ref->cend()); + } + + // iterator, mutable, read-write + + constexpr iterator begin() noexcept { + return iterator(*this, [](storage_ref_t& new_store) -> iterator { return new_store->begin(); } ); + } + + constexpr iterator end() noexcept { + return iterator(*this, [](storage_ref_t& new_store) -> iterator { return new_store->end(); } ); + } + + // read access + + const Alloc_type& get_allocator_ref() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref->get_allocator_ref(); + } + + Alloc_type get_allocator() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref->get_allocator(); + } + + constexpr Size_type capacity() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref->capacity(); + } + + /** + * Like std::vector::empty(). + * <p> + * This read operation is <i>lock-free</i>. + * </p> + */ + constexpr bool empty() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref->empty(); + } + + /** + * Like std::vector::size(). + * <p> + * This read operation is <i>lock-free</i>. + * </p> + */ + constexpr Size_type size() const noexcept { + sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); + return store_ref->size(); + } + + // write access + + /** + * Like std::vector::reserve(), increases this instance's capacity to <code>new_capacity</code>. + * <p> + * Only creates a new storage and invalidates iterators if <code>new_capacity</code> + * is greater than the current jau::darray::capacity(). + * </p> + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + void reserve(Size_type new_capacity) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + if( new_capacity > old_store_ref->capacity() ) { + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_capacity, + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + sc_atomic_critical sync( sync_atomic ); + store_ref = std::move(new_store_ref); + } + } + + /** + * Like std::vector::operator=(&), assignment, but copying from the underling jau::darray + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + cow_darray& operator=(const storage_t& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>( x ); + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + return *this; + } + + /** + * Like std::vector::operator=(&&), move, but taking the underling jau::darray + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + cow_darray& operator=(storage_t&& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>( std::move(x) ); + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + return *this; + } + + /** + * Like std::vector::operator=(&), assignment + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + cow_darray& operator=(const cow_darray& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t x_store_ref; + { + sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic ); + x_store_ref = x.store_ref; + } + storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref ); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + return *this; + } + + /** + * Like std::vector::operator=(&&), move. + * <p> + * This write operation uses a mutex lock and is blocking both cow_vector instance's write operations. + * </p> + */ + cow_darray& operator=(cow_darray&& x) { + std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object + std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor + std::lock(lock, lock_x); + { + sc_atomic_critical sync_x( x.sync_atomic ); + sc_atomic_critical sync(sync_atomic); + // swap store_ref + store_ref = std::move(x.store_ref); + x.store_ref = nullptr; + } + return *this; + } + + /** + * Like std::vector::clear(), but ending with zero capacity. + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations. + * </p> + */ + void clear() noexcept { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>(); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } + + /** + * Like std::vector::swap(). + * <p> + * This write operation uses a mutex lock and is blocking both cow_darray instance's write operations. + * </p> + */ + void swap(cow_darray& x) noexcept { + std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object + std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor + std::lock(lock, lock_x); + { + sc_atomic_critical sync_x( x.sync_atomic ); + sc_atomic_critical sync(sync_atomic); + storage_ref_t x_store_ref = x.store_ref; + x.store_ref = store_ref; + store_ref = x_store_ref; + } + } + + /** + * Like std::vector::pop_back(). + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + void pop_back() noexcept { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + if( !old_store_ref->empty() ) { + storage_ref_t new_store_ref = std::make_shared<storage_t>( old_store_ref->capacity(), + old_store_ref->cbegin(), + old_store_ref->cend()-1, + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } + } + + /** + * Like std::vector::push_back(), copy + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * @param x the value to be added at the tail. + */ + void push_back(const Value_type& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + if( old_store_ref->capacity_reached() ) { + // grow and swap all refs + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->grow_capacity(), + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + new_store_ref->push_back(x); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } else { + // just append .. + store_ref->push_back(x); + } + } + + /** + * Like std::vector::push_back(), move + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + */ + void push_back(Value_type&& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + if( old_store_ref->capacity_reached() ) { + // grow and swap all refs + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->grow_capacity(), + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + new_store_ref->push_back( std::move(x) ); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } else { + // just append .. + store_ref->push_back( std::move(x) ); + } + } + + /** + * Like std::vector::push_back(), but appends the whole Value_type range [first, last). + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * @tparam InputIt foreign input-iterator to range of Value_type [first, last) + * @param first first foreign input-iterator to range of Value_type [first, last) + * @param last last foreign input-iterator to range of Value_type [first, last) + */ + template< class InputIt > + constexpr void push_back( InputIt first, InputIt last ) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + const Size_type new_size_ = old_store_ref->size() + Size_type(last - first); + + if( new_size_ > old_store_ref->capacity() ) { + // grow and swap all refs + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_size_, + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + store_ref->push_back( first, last ); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } else { + // just append .. + store_ref->push_back( first, last ); + } + } + + /** + * Like std::vector::push_back(), but appends the whole Value_type range [first, last). + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * @param first first const_iterator to range of Value_type [first, last) + * @param last last const_iterator to range of Value_type [first, last) + */ + constexpr void push_back( const_iterator first, const_iterator last ) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t old_store_ref = store_ref; + const Size_type new_size_ = old_store_ref->size() + Size_type(last - first); + + if( new_size_ > old_store_ref->capacity() ) { + // grow and swap all refs + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_size_, + old_store_ref->growth_factor(), + old_store_ref->get_allocator_ref() ); + store_ref->push_back( first.underling(), last.underling() ); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } else { + // just append .. + store_ref->push_back( first.underling(), last.underling() ); + } + } + + /** + * Generic Value_type equal comparator to be user defined for e.g. jau::cow_darray::push_back_unique(). + * @param a one element of the equality test. + * @param b the other element of the equality test. + * @return true if both are equal + */ + typedef bool(*equal_comparator)(const Value_type& a, const Value_type& b); + + /** + * Like std::vector::push_back(), but only if the newly added element does not yet exist. + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * <p> + * Examples + * <pre> + * static jau::cow_darray<Thing>::equal_comparator thingEqComparator = + * [](const Thing &a, const Thing &b) -> bool { return a == b; }; + * ... + * jau::cow_darray<Thing> list; + * + * bool added = list.push_back_unique(new_element, thingEqComparator); + * ... + * cow_darray<std::shared_ptr<Thing>> listOfRefs; + * bool added = listOfRefs.push_back_unique(new_element, + * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; }); + * </pre> + * </p> + * @param x the value to be added at the tail, if not existing yet. + * @param comparator the equal comparator to return true if both given elements are equal + * @return true if the element has been uniquely added, otherwise false + */ + bool push_back_unique(const Value_type& x, equal_comparator comparator) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + for(auto it = store_ref->begin(); it != store_ref->end(); ) { + if( comparator( *it, x ) ) { + return false; // already included + } else { + ++it; + } + } + push_back(x); + return true; + } + + /** + * Erase either the first matching element or all matching elements. + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * <p> + * Examples + * <pre> + * cow_darray<Thing> list; + * int count = list.erase_matching(element, true, + * [](const Thing &a, const Thing &b) -> bool { return a == b; }); + * ... + * static jau::cow_darray<Thing>::equal_comparator thingRefEqComparator = + * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; }; + * ... + * cow_darray<std::shared_ptr<Thing>> listOfRefs; + * int count = listOfRefs.erase_matching(element, false, thingRefEqComparator); + * </pre> + * </p> + * @param x the value to be added at the tail, if not existing yet. + * @param all_matching if true, erase all matching elements, otherwise only the first matching element. + * @param comparator the equal comparator to return true if both given elements are equal + * @return number of erased elements + */ + int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) { + int count = 0; + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref ); + for(auto it = new_store_ref->begin(); it != new_store_ref->end(); ) { + if( comparator( *it, x ) ) { + it = new_store_ref->erase(it); + ++count; + if( !all_matching ) { + break; + } + } else { + ++it; + } + } + if( 0 < count ) { // mutated new_store_ref? + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } // else throw away new_store_ref + return count; + } + + /** + * Thread safe Value_type copy assignment to Value_type at given position with bounds checking. + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * <p> + * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end(). + * </p> + * @param i the position within this store + * @param x the value to be assigned to the object at the given position + */ + void put(size_t i, const Value_type& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref ); + new_store_ref->at(i) = x; + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } + + /** + * Thread safe Value_type move assignment to Value_type at given position with bounds checking. + * <p> + * This write operation uses a mutex lock and is blocking this instances' write operations only. + * </p> + * <p> + * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end(). + * </p> + * @param i the position within this store + * @param x the value to be assigned to the object at the given position + */ + void put(size_t i, Value_type&& x) { + const std::lock_guard<std::recursive_mutex> lock(mtx_write); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref ); + new_store_ref->at(i) = std::move(x); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } + } + }; + +} /* namespace jau */ + +#endif /* JAU_COW_DARRAY_HPP_ */ diff --git a/include/jau/cow_iterator.hpp b/include/jau/cow_iterator.hpp new file mode 100644 index 0000000..8ebd9c1 --- /dev/null +++ b/include/jau/cow_iterator.hpp @@ -0,0 +1,254 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright (c) 2020 Gothel Software e.K. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef JAU_COW_ITERATOR_HPP_ +#define JAU_COW_ITERATOR_HPP_ + +#include <cstddef> +#include <mutex> + +namespace jau { + + /** + * Implementation of a Copy-On-Write (CoW) read-only iterator for immutable Value_type, + * holding the shared Value_type& of the current CoW storage until destruction. + */ + template <typename Value_type, typename Storage_type, typename Storage_ref_type> + class cow_ro_iterator { + + private: + Storage_ref_type store_holder_; + typename Storage_type::const_iterator iterator_; + + public: + constexpr cow_ro_iterator(Storage_ref_type store, typename Storage_type::const_iterator iter) + : store_holder_(store), iterator_(iter) {} + + constexpr explicit cow_ro_iterator(const cow_ro_iterator& o) noexcept + : store_holder_(o.store_holder_), iterator_(o.iterator_) {} + + /** + * Returns a copy of the underlying storage const_iterator. + */ + typename Storage_type::const_iterator underling() const noexcept { return iterator_; }; + + // Multipass guarantee equality + + constexpr bool operator==(const cow_ro_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + // only testing identity of pointer, OK for Multipass guarantee + return store_holder_ == rhs.store_holder_ && + iterator_ == rhs.iterator_; + } + constexpr bool operator!=(const cow_ro_iterator& rhs) const noexcept + { return !(*this == rhs); } + + // Forward iterator requirements + + constexpr const Value_type& operator*() const noexcept + { return *iterator_; } + + constexpr const Value_type* operator->() const noexcept + { return iterator_; } + + /** Pre-increment; Well performing, return *this. */ + constexpr cow_ro_iterator& operator++() noexcept { + ++iterator_; + return *this; + } + + /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_ro_iterator& operator++(int) noexcept + { return cow_ro_iterator(store_holder_, iterator_++); } + + // Bidirectional iterator requirements + + /** Pre-decrement; Well performing, return *this. */ + constexpr cow_ro_iterator& operator--() noexcept { + --iterator_; + return *this; + } + + /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_ro_iterator& operator--(int) noexcept + { return cow_iterator(store_holder_, iterator_--); } + + // Random access iterator requirements + + /** Subscript of 'element_index', returning immutable Value_type reference. */ + constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept + { return iterator_[i]; } + + /** Addition-assignment of 'element_count'; Well performing, return *this. */ + constexpr cow_ro_iterator& operator+=(std::ptrdiff_t i) noexcept + { iterator_ += i; return *this; } + + /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_ro_iterator operator+(std::ptrdiff_t rhs) const noexcept + { return cow_iterator(store_holder_, iterator_ + rhs); } + + /** Subtraction-assignment of 'element_count'; Well performing, return *this. */ + constexpr cow_ro_iterator& operator-=(std::ptrdiff_t i) noexcept + { iterator_ -= i; return *this; } + + /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_ro_iterator operator-(std::ptrdiff_t rhs) const noexcept + { return cow_iterator(store_holder_, iterator_ - rhs); } + + // Distance or element count, binary subtraction of two iterator. + + /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */ + constexpr std::ptrdiff_t operator-(const cow_ro_iterator& rhs) const noexcept + { return iterator_ - rhs.iterator_; } + }; + + /** + * Implementation of a Copy-On-Write (CoW) read-write iterator for mutable Value_type, + * holding the write lock, a new copy of the CoW storage and a Value_type& of the CoW container itself. + * <p> + * At destruction, the mutated local storage will replace the + * storage in the CoW container and the lock will be released. + * </p> + */ + template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename CoW_container> + class cow_rw_iterator { + + private: + CoW_container& cow_parent_; + const std::lock_guard<std::recursive_mutex> lock_; + Storage_ref_type new_store_; + typename Storage_type::iterator iterator_; + + constexpr explicit cow_rw_iterator(CoW_container& cow_parent, Storage_ref_type& store, typename Storage_type::iterator iter) noexcept + : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(store), iterator_(iter) {} + + public: + constexpr cow_rw_iterator(CoW_container& cow_parent, typename Storage_type::iterator (*get_iterator)(Storage_ref_type&)) + : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(cow_parent.copy_store()), iterator_(get_iterator(new_store_)) {} + +#if __cplusplus > 201703L + constexpr ~cow_rw_iterator() noexcept +#else + ~cow_rw_iterator() noexcept +#endif + { + cow_parent_.set_store(std::move(new_store_)); + } + + /** + * Returns a copy of the underlying storage iterator. + */ + typename Storage_type::iterator underling() const noexcept { return iterator_; }; + + // Multipass guarantee equality + + constexpr bool operator==(const cow_rw_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + // only testing identity of pointer, OK for Multipass guarantee + return &cow_parent_ == &rhs.cow_parent_ && + new_store_ == rhs.new_store_ && + iterator_ == rhs.iterator_; + } + constexpr bool operator!=(const cow_rw_iterator& rhs) const noexcept + { return !(*this == rhs); } + + // Forward iterator requirements + + constexpr const Value_type& operator*() const noexcept + { return *iterator_; } + + constexpr const Value_type* operator->() const noexcept + { return iterator_; } + + constexpr Value_type& operator*() noexcept + { return *iterator_; } + + constexpr Value_type* operator->() noexcept + { return iterator_; } + + /** Pre-increment; Well performing, return *this. */ + constexpr cow_rw_iterator& operator++() noexcept { + ++iterator_; + return *this; + } + + /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_rw_iterator& operator++(int) noexcept + { return cow_rw_iterator(cow_parent_, new_store_, iterator_++); } + + // Bidirectional iterator requirements + + /** Pre-decrement; Well performing, return *this. */ + constexpr cow_rw_iterator& operator--() noexcept { + --iterator_; + return *this; + } + + /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_rw_iterator& operator--(int) noexcept + { return cow_rw_iterator(cow_parent_, new_store_, iterator_--); } + + // Random access iterator requirements + + /** Subscript of 'element_index', returning immutable Value_type reference. */ + constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept + { return iterator_[i]; } + + /** Subscript of 'element_index', returning mutable Value_type reference. */ + constexpr Value_type& operator[](std::ptrdiff_t i) noexcept + { return iterator_[i]; } + + /** Addition-assignment of 'element_count'; Well performing, return *this. */ + constexpr cow_rw_iterator& operator+=(std::ptrdiff_t i) noexcept + { iterator_ += i; return *this; } + + /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_rw_iterator operator+(std::ptrdiff_t rhs) const noexcept + { return cow_rw_iterator(cow_parent_, new_store_, iterator_ + rhs); } + + /** Subtraction-assignment of 'element_count'; Well performing, return *this. */ + constexpr cow_rw_iterator& operator-=(std::ptrdiff_t i) noexcept + { iterator_ -= i; return *this; } + + /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */ + constexpr cow_rw_iterator operator-(std::ptrdiff_t rhs) const noexcept + { return cow_rw_iterator(cow_parent_, new_store_, iterator_ - rhs); } + + // constexpr const cow_rw_iterator& base() const noexcept + // { return iterator_; } + + // Distance or element count, binary subtraction of two iterator. + + /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */ + constexpr std::ptrdiff_t operator-(const cow_rw_iterator& rhs) const noexcept + { return iterator_ - rhs.iterator_; } + }; + +} /* namespace jau */ + +#endif /* JAU_COW_ITERATOR_HPP_ */ diff --git a/include/jau/cow_vector.hpp b/include/jau/cow_vector.hpp index 251e130..cc35ffa 100644 --- a/include/jau/cow_vector.hpp +++ b/include/jau/cow_vector.hpp @@ -39,15 +39,15 @@ #include <jau/debug.hpp> #include <jau/basic_types.hpp> #include <jau/ordered_atomic.hpp> - +#include <jau/cow_iterator.hpp> namespace jau { /** - * Implementation of a Copy-On-Write (CoW) vector, + * Implementation of a Copy-On-Write (CoW) using std::vector as the underlying storage, * exposing <i>lock-free</i> read operations using SC-DRF atomic synchronization. * <p> - * The vector's store is owned using a reference to the data structure, + * The vector's store is owned using a shared reference to the data structure, * allowing its replacement on Copy-On-Write (CoW). * </p> * <p> @@ -61,10 +61,22 @@ namespace jau { * jau::sc_atomic_critical to synchronizing with write operations. * </p> * <p> - * Naturally iterators are not supported directly, - * otherwise we would need to copy the store to iterate through.<br> - * However, one can utilize iteration using the shared snapshot - * of the underlying vector store via jau::cow_vector::get_snapshot() for read operations. + * Immutable storage const_iterators are supported via jau::cow_ro_iterator, + * which are constructed <i>lock-free</i>.<br> + * jau::cow_ro_iterator hold a snapshot retrieved via jau::cow_vector::get_snapshot() + * until its destruction. + * </p> + * <p> + * Mutable storage iterators are supported via jau::cow_rw_iterator, + * which are constructed holding the write-lock.<br> + * jau::cow_rw_iterator hold a new store copy via jau::cow_vector::copy_store(), + * which replaces the current store via jau::cow_vector::set_store() at destruction. + * </p> + * <p> + * Index operation via ::operator[](size_t) or ::at(size_t) are not supported for now, + * since they would be only valid if Value_type itself is a std::shared_ptr + * and hence prohibit the destruction of the object if mutating the storage, + * e.g. via jau::cow_vector::push_back(). * </p> * <p> * Custom mutable write operations are also supported via @@ -76,54 +88,78 @@ namespace jau { * - Sequentially Consistent (SC) ordering or SC-DRF (data race free) <https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering> * - std::memory_order <https://en.cppreference.com/w/cpp/atomic/memory_order> * </pre> + * \deprecated { jau::cow_vector will be retired, use jau::cow_darray and potentially jau::darray. } */ - template <typename Value_type, typename Alloc_type = std::allocator<Value_type>> class cow_vector { - private: - typedef std::vector<Value_type, Alloc_type> vector_t; - typedef std::shared_ptr<vector_t> vector_ref; + template <typename Value_type, typename Alloc_type = std::allocator<Value_type>> + class cow_vector + { + public: + typedef std::vector<Value_type, Alloc_type> storage_t; + typedef std::shared_ptr<storage_t> storage_ref_t; + + /** + * Immutable, read-only const_iterator, lock-free, + * holding the current shared store reference until destruction. + * <p> + * Using jau::cow_vector::get_snapshot() at construction. + * </p> + */ + typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator; + + /** + * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. + * <p> + * Using jau::cow_vector::get_write_mutex(), jau::cow_vector::copy_store() at construction<br> + * and jau::cow_vector::set_store() at destruction. + * </p> + */ + typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_vector> iterator; - vector_ref store_ref; + private: + storage_ref_t store_ref; sc_atomic_bool sync_atomic; std::recursive_mutex mtx_write; public: // ctor - cow_vector() noexcept - : store_ref( std::make_shared<vector_t>() ), sync_atomic(false) {} + constexpr cow_vector() noexcept + : store_ref( std::make_shared<storage_t>() ), sync_atomic(false) {} - explicit cow_vector(const Alloc_type & a) noexcept - : store_ref( std::make_shared<vector_t>(a) ), sync_atomic(false) { } + constexpr explicit cow_vector(const Alloc_type & a) noexcept + : store_ref( std::make_shared<storage_t>(a) ), sync_atomic(false) { } - explicit cow_vector(size_t n, const Alloc_type& a = Alloc_type()) - : store_ref( std::make_shared<vector_t>(n, a) ), sync_atomic(false) { } + constexpr explicit cow_vector(size_t n, const Alloc_type& a = Alloc_type()) + : store_ref( std::make_shared<storage_t>(n, a) ), sync_atomic(false) { } - cow_vector(size_t n, const Value_type& value, const Alloc_type& a = Alloc_type()) - : store_ref( std::make_shared<vector_t>(n, value, a) ), sync_atomic(false) { } + constexpr cow_vector(size_t n, const Value_type& value, const Alloc_type& a = Alloc_type()) + : store_ref( std::make_shared<storage_t>(n, value, a) ), sync_atomic(false) { } - cow_vector(const cow_vector& x) + constexpr cow_vector(const cow_vector& x) : sync_atomic(false) { - vector_ref x_store_ref; + storage_ref_t x_store_ref; { sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic ); x_store_ref = x.store_ref; } - store_ref = std::make_shared<vector_t>( *x_store_ref, x_store_ref->get_allocator() ); + store_ref = std::make_shared<storage_t>( *x_store_ref, x_store_ref->get_allocator() ); } - explicit cow_vector(const vector_t& x) - : store_ref( std::make_shared<vector_t>(x, x->get_allocator()) ), sync_atomic(false) { } + constexpr explicit cow_vector(const storage_t& x) + : store_ref( std::make_shared<storage_t>(x, x->get_allocator()) ), sync_atomic(false) { } - cow_vector(cow_vector && x) noexcept { + constexpr cow_vector(cow_vector && x) noexcept { // swap store_ref - store_ref = x.store_ref; + store_ref = std::move(x.store_ref); x.store_ref = nullptr; // not really necessary - sync_atomic = x.sync_atomic; + sync_atomic = std::move(x.sync_atomic); } ~cow_vector() noexcept { } + // cow_vector features + /** * Returns this instances' recursive write mutex, allowing user to * implement more complex mutable write operations. @@ -135,7 +171,7 @@ namespace jau { * @see jau::cow_vector::copy_store() * @see jau::cow_vector::set_store() */ - std::recursive_mutex & get_write_mutex() { return mtx_write; } + constexpr std::recursive_mutex & get_write_mutex() noexcept { return mtx_write; } /** * Returns a new shared_ptr copy of the underlying store, @@ -150,9 +186,9 @@ namespace jau { * @see jau::cow_vector::copy_store() * @see jau::cow_vector::set_store() */ - std::shared_ptr<std::vector<Value_type>> copy_store() noexcept { + storage_ref_t copy_store() { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - return std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + return std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); } /** @@ -182,14 +218,12 @@ namespace jau { * @see jau::cow_vector::copy_store() * @see jau::cow_vector::set_store() */ - void set_store(std::shared_ptr<std::vector<Value_type>> && new_store_ref) noexcept { + constexpr void set_store(storage_ref_t && new_store_ref) noexcept { const std::lock_guard<std::recursive_mutex> lock(mtx_write); sc_atomic_critical sync(sync_atomic); - store_ref = new_store_ref; + store_ref = std::move( new_store_ref ); } - // read access - /** * Returns the current snapshot of the underlying shared std::vector<T> reference. * <p> @@ -202,17 +236,47 @@ namespace jau { * </p> * @see jau::for_each_cow */ - std::shared_ptr<std::vector<Value_type>> get_snapshot() const noexcept { + constexpr storage_ref_t get_snapshot() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref; } + // const_iterator, non mutable, read-only + + constexpr const_iterator begin() const noexcept { + return const_iterator(get_snapshot(), store_ref->cbegin()); + } + + constexpr const_iterator cbegin() const noexcept { + return const_iterator(get_snapshot(), store_ref->cbegin()); + } + + constexpr const_iterator end() const noexcept { + return const_iterator(get_snapshot(), store_ref->cend()); + } + + constexpr const_iterator cend() const noexcept { + return const_iterator(get_snapshot(), store_ref->cend()); + } + + // iterator, mutable, read-write + + constexpr iterator begin() noexcept { + return iterator(*this, store_ref->begin()); + } + + constexpr iterator end() noexcept { + return iterator(*this, store_ref->end()); + } + + // read access + Alloc_type get_allocator() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->get_allocator(); } - std::size_t capacity() const noexcept { + constexpr std::size_t capacity() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->capacity(); } @@ -223,7 +287,7 @@ namespace jau { * This read operation is <i>lock-free</i>. * </p> */ - bool empty() const noexcept { + constexpr bool empty() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->empty(); } @@ -234,11 +298,12 @@ namespace jau { * This read operation is <i>lock-free</i>. * </p> */ - size_t size() const noexcept { + constexpr size_t size() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->size(); } +#if 0 /** * Like std::vector::operator[](size_t). * <p> @@ -292,13 +357,19 @@ namespace jau { sc_atomic_critical sync(sync_atomic); return store_ref->at(i); } +#endif // write access - void reserve(std::size_t n) { + void reserve(std::size_t new_capacity) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); - store_ref->reserve(n); + storage_ref_t old_store_ref = store_ref; + if( new_capacity > old_store_ref->capacity() ) { + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->get_allocator() ); + new_store_ref->reserve(new_capacity); + sc_atomic_critical sync( sync_atomic ); + store_ref = std::move(new_store_ref); + } } /** @@ -309,12 +380,12 @@ namespace jau { */ cow_vector& operator=(const cow_vector& x) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref x_store_ref; + storage_ref_t x_store_ref; { sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic ); x_store_ref = x.store_ref; } - vector_ref new_store_ref = std::make_shared<vector_t>( *x_store_ref, x_store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref, x_store_ref->get_allocator() ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); @@ -325,15 +396,20 @@ namespace jau { /** * Like std::vector::operator=(&&), move. * <p> - * This write operation uses a mutex lock and is blocking this instances' write operations only. + * This write operation uses a mutex lock and is blocking both cow_vector instance's write operations. * </p> */ cow_vector& operator=(cow_vector&& x) { - const std::lock_guard<std::recursive_mutex> lock(mtx_write); - sc_atomic_critical sync(sync_atomic); - // swap store_ref - store_ref = std::move(x.store_ref); - x.store_ref = nullptr; + std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object + std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor + std::lock(lock, lock_x); + { + sc_atomic_critical sync_x( x.sync_atomic ); + sc_atomic_critical sync(sync_atomic); + // swap store_ref + store_ref = std::move(x.store_ref); + x.store_ref = nullptr; + } return *this; } @@ -345,7 +421,7 @@ namespace jau { */ void clear() noexcept { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>(); + storage_ref_t new_store_ref = std::make_shared<storage_t>(); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); @@ -363,9 +439,9 @@ namespace jau { std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor std::lock(lock, lock_x); { - sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic ); + sc_atomic_critical sync_x( x.sync_atomic ); sc_atomic_critical sync(sync_atomic); - vector_ref x_store_ref = x.store_ref; + storage_ref_t x_store_ref = x.store_ref; x.store_ref = store_ref; store_ref = x_store_ref; } @@ -379,11 +455,14 @@ namespace jau { */ void pop_back() noexcept { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); - new_store_ref->pop_back(); - { - sc_atomic_critical sync(sync_atomic); - store_ref = std::move(new_store_ref); + storage_ref_t old_store_ref = store_ref; + if( 0 < old_store_ref->size() ) { + storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->get_allocator() ); + new_store_ref->pop_back(); + { + sc_atomic_critical sync(sync_atomic); + store_ref = std::move(new_store_ref); + } } } @@ -396,7 +475,7 @@ namespace jau { */ void push_back(const Value_type& x) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); new_store_ref->push_back(x); { sc_atomic_critical sync(sync_atomic); @@ -412,7 +491,7 @@ namespace jau { */ void push_back(Value_type&& x) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); new_store_ref->push_back( std::move(x) ); { sc_atomic_critical sync(sync_atomic); @@ -461,7 +540,7 @@ namespace jau { ++it; } } - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); new_store_ref->push_back(x); { sc_atomic_critical sync(sync_atomic); @@ -497,11 +576,11 @@ namespace jau { int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) { int count = 0; const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); for(auto it = new_store_ref->begin(); it != new_store_ref->end(); ) { if( comparator( *it, x ) ) { it = new_store_ref->erase(it); - count++; + ++count; if( !all_matching ) { break; } @@ -521,12 +600,15 @@ namespace jau { * <p> * This write operation uses a mutex lock and is blocking this instances' write operations only. * </p> + * <p> + * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end(). + * </p> * @param i the position within this store * @param x the value to be assigned to the object at the given position */ void put(size_t i, const Value_type& x) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); new_store_ref->at(i) = x; { sc_atomic_critical sync(sync_atomic); @@ -539,12 +621,15 @@ namespace jau { * <p> * This write operation uses a mutex lock and is blocking this instances' write operations only. * </p> + * <p> + * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end(). + * </p> * @param i the position within this store * @param x the value to be assigned to the object at the given position */ void put(size_t i, Value_type&& x) { const std::lock_guard<std::recursive_mutex> lock(mtx_write); - vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() ); + storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() ); new_store_ref->at(i) = std::move(x); { sc_atomic_critical sync(sync_atomic); @@ -553,29 +638,6 @@ namespace jau { } }; - /** - * Custom for_each template on a jau::cow_vector snapshot - * using jau::cow_vector::get_snapshot(). - * <p> - * jau::for_each_idx() would also be usable, however, - * iterating through the snapshot preserves consistency over the - * fetched collection at the time of invocation. - * </p> - * <p> - * Method performs UnaryFunction on all snapshot elements [0..n-1]. - * </p> - */ - template<typename Value_type, class UnaryFunction> - constexpr UnaryFunction for_each_cow(cow_vector<Value_type> &cow, UnaryFunction f) - { - std::shared_ptr<std::vector<Value_type>> snapshot = cow.get_snapshot(); - const size_t size = snapshot->size(); - for (size_t i = 0; i < size; i++) { - f( (*snapshot)[i] ); - } - return f; // implicit move since C++11 - } - } /* namespace jau */ #endif /* JAU_COW_VECTOR_HPP_ */ diff --git a/include/jau/darray.hpp b/include/jau/darray.hpp new file mode 100644 index 0000000..dc81b60 --- /dev/null +++ b/include/jau/darray.hpp @@ -0,0 +1,821 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright (c) 2020 Gothel Software e.K. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef JAU_DYN_ARRAY_HPP_ +#define JAU_DYN_ARRAY_HPP_ + +#include <cstring> +#include <string> +#include <cstdint> +#include <atomic> +#include <memory> +#include <mutex> +#include <condition_variable> +#include <vector> +#include <algorithm> + +#include <jau/debug.hpp> +#include <jau/basic_types.hpp> +#include <jau/ordered_atomic.hpp> + + +namespace jau { + + /** + * Implementation of a dynamic linear array storage, aka vector.<br> + * Goals are to support a high-performance CoW dynamic array implementation, jau::cow_darray,<br> + * exposing fine grained control over its underlying storage facility.<br> + * Further, jau::darray provides high-performance and efficient storage properties on its own. + * <p> + * API and design differences to std::vector + * <ul> + * <li>jau::darray adds a parameterized <i>growth factor</i> aspect, default to golden ration jau::darray::DEFAULT_GROWTH_FACTOR</li> + * <li><i>capacity</i> control via constructor and operations, related to <i>growth factor</i>.</li> + * <li>Iterator jau::darray::const_iterator .. are harmonized with jau::cow_ro_iterator .. used in jau:cow_darray.</li> + * <li>...</li> + * <li>Custom constructor and operations, supporting a more efficient jau::cow_darray implementation.</li> + * <li>Custom template typename Size_type, defaults to jau::nsize_t.</li> + * <li>...</li> + * <li><b>Removed</b>: Size_type x Value_type fill operations, e.g. assign, constructor, .... for clarity, since supporting <i>capacity</i>.</li> + * <li>...</li> + * <li><b>TODO</b>: emplace(..), list-initialization operations</li> + * </ul> + * </p> + * <p> + * Implementation differences to std::vector and some details + * <ul> + * <li>Using zero overhead <i>Value_type*</i> as iterator type.</li> + * <li>...</li> + * <li>Storage is operated on three iterator: <i>begin</i>, <i>end</i> and <i>storage_end</i>.</li> + * <li>Constructs and destructs Value_type via <i>placement new</i> within the pre-allocated array capacity. Latter is managed via Alloc_type.</li> + * </ul> + * </p> + */ + template <typename Value_type, typename Alloc_type = std::allocator<Value_type>, typename Size_type = jau::nsize_t> + class darray + { + public: + /** Default growth factor using the golden ratio 1.618 */ + inline static const float DEFAULT_GROWTH_FACTOR = 1.618f; + + typedef Value_type* iterator; + typedef const Value_type* const_iterator; + + private: + inline static void freeStore(Alloc_type& alloc, Value_type *ptr, const Size_type size) { + if( nullptr != ptr ) { + alloc.deallocate(ptr, size); + } + } + + inline static Value_type * allocStore(Alloc_type& alloc, const Size_type size) { + if( 0 < size ) { + Value_type * m = alloc.allocate(size); + if( nullptr == m ) { + throw jau::OutOfMemoryError("allocData "+std::to_string(size)+" elements * "+ + std::to_string(sizeof(Value_type))+" bytes/element = "+ + std::to_string(size * sizeof(Value_type))+" bytes -> nullptr", E_FILE_LINE); + } + return m; + } + return nullptr; + } + + typedef Value_type* array_ref; + + float growth_factor_; + Alloc_type alloc_inst; + array_ref begin_; + array_ref end_; + array_ref storage_end_; + + constexpr void set_iterator(array_ref new_storage_, Size_type size_, Size_type capacity_) noexcept { + begin_ = new_storage_; + end_ = new_storage_+size_; + storage_end_ = new_storage_+capacity_; + } + + constexpr void set_iterator(Size_type size_, Size_type capacity_) noexcept { + end_ = begin_+size_; + storage_end_ = begin_+capacity_; + } + + Size_type dtor_range(array_ref first, const array_ref last) { + Size_type count=0; + for(; first < last; ++first, ++count ) { + ( first )->~Value_type(); // placement new -> manual destruction! + } + return count; + } + + inline static void ctor_copy_range(array_ref dest, array_ref first, const array_ref last) { + for(; first < last; ++dest, ++first) { + new (dest) Value_type( *first ); // placement new + } + } + static array_ref clone_range(Alloc_type& alloc, const Size_type dest_capacity, const array_ref first, const array_ref last) { + if( dest_capacity < Size_type(last-first) ) { + throw jau::IllegalArgumentException("capacity "+std::to_string(dest_capacity)+" < source range "+ + std::to_string(Size_type(last-first)), E_FILE_LINE); + } + array_ref dest = allocStore(alloc, dest_capacity); + ctor_copy_range(dest, first, last); + return dest; + } + static array_ref clone_range(Alloc_type& alloc, const array_ref first, const array_ref last) { + array_ref dest = allocStore(alloc, Size_type(last-first)); + ctor_copy_range(dest, first, last); + return dest; + } + + template< class InputIt > + inline static void ctor_copy_range_foreign(array_ref dest, InputIt first, InputIt last) { + for(; first < last; ++dest, ++first) { + new (dest) Value_type( *first ); // placement new + } + } + template< class InputIt > + static array_ref clone_range_foreign(Alloc_type& alloc, const Size_type dest_capacity, InputIt first, InputIt last) { + if( dest_capacity < Size_type(last-first) ) { + throw jau::IllegalArgumentException("capacity "+std::to_string(dest_capacity)+" < source range "+ + std::to_string(Size_type(last-first)), E_FILE_LINE); + } + array_ref dest = allocStore(alloc, dest_capacity); + ctor_copy_range_foreign(dest, first, last); + return dest; + } + + inline static void ctor_move_range(array_ref dest, array_ref first, const array_ref last) { + for(; first < last; ++dest, ++first) { + new (dest) Value_type( std::move( *first ) ); // placement new + } + } + void grow_storage_move(const Size_type new_capacity) { + array_ref dest = allocStore(alloc_inst, new_capacity); + ctor_move_range(dest, begin_, end_); + + freeStore(alloc_inst, begin_, capacity()); + + set_iterator(dest, size(), new_capacity); + } + + public: + + // ctor w/o elements + + /** + * Default constructor, giving zero capacity and zero memory footprint. + */ + constexpr darray() noexcept + : growth_factor_(DEFAULT_GROWTH_FACTOR), alloc_inst(), + begin_( nullptr ), end_( nullptr ), storage_end_( nullptr ) {} + + /** + * Creating an empty instance with initial capacity and other (default) properties. + * @param capacity initial capacity of the new instance. + * @param growth_factor given growth factor + * @param alloc given Alloc_type + */ + constexpr explicit darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( allocStore(alloc_inst, capacity) ), + end_( begin_ ), storage_end_( begin_ + capacity ) {} + + // copy_ctor on darray elements + + /** + * Creates a new instance, copying all elements from the given darray.<br> + * Capacity and size will equal the given array, i.e. the result is a trimmed jau::darray. + * @param x the given darray, all elements will be copied into the new instance. + */ + constexpr darray(const darray& x) + : growth_factor_( x.growth_factor_ ), alloc_inst( x.alloc_inst ), begin_( clone_range(alloc_inst, x.begin_, x.end_) ), + end_( begin_ + x.size() ), storage_end_( begin_ + x.size() ) + { } + + /** + * Creates a new instance, copying all elements from the given darray.<br> + * Capacity and size will equal the given array, i.e. the result is a trimmed jau::darray. + * @param x the given darray, all elements will be copied into the new instance. + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr explicit darray(const darray& x, const float growth_factor, const Alloc_type& alloc) + : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, x.begin_, x.end_) ), + end_( begin_ + x.size() ), storage_end_( begin_ + x.size() ) + { } + + /** + * Creates a new instance with custom initial storage capacity, copying all elements from the given darray.<br> + * Size will equal the given array. + * <p> + * Throws jau::IllegalArgumentException() if <code>_capacity < x.size()</code>. + * </p> + * @param x the given darray, all elements will be copied into the new instance. + * @param _capacity custom initial storage capacity + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr explicit darray(const darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc) + : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, _capacity, x.begin_, x.end_) ), + end_( begin_ + x.size() ), storage_end_( begin_ + _capacity ) + { } + + // move_ctor on darray elements + + constexpr darray(darray && x) noexcept + : growth_factor_(std::move(x.growth_factor_)), alloc_inst(std::move(x.alloc_inst)), + begin_(std::move(x.begin_)), end_(std::move(x.end_)), storage_end_(std::move(x.storage_end_)) + { + // complete swapping store_ref + x.begin_ = nullptr; + x.end_ = nullptr; + x.storage_end_ = nullptr; + } + + constexpr explicit darray(darray && x, const float growth_factor, const Alloc_type& alloc) noexcept + : growth_factor_(std::move(x.growth_factor_)), alloc_inst(alloc), + begin_(std::move(x.begin_)), end_(std::move(x.end_)), storage_end_(std::move(x.storage_end_)) + { + // complete swapping store_ref + x.begin_ = nullptr; + x.end_ = nullptr; + x.storage_end_ = nullptr; + } + + // ctor on const_iterator and foreign template iterator + + /** + * Creates a new instance with custom initial storage capacity, + * copying all elements from the given const_iterator Value_type range [first, last).<br> + * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>. + * <p> + * Throws jau::IllegalArgumentException() if <code>_capacity < Size_type(last - first)</code>. + * </p> + * @param _capacity custom initial storage capacity + * @param first const_iterator to first element of Value_type range [first, last) + * @param last const_iterator to last element of Value_type range [first, last) + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + constexpr darray(const Size_type _capacity, const_iterator first, const_iterator last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, _capacity, first, last) ), + end_(begin_ + Size_type(last - first) ), storage_end_( begin_ + _capacity ) + { } + + /** + * Creates a new instance with custom initial storage capacity, + * copying all elements from the given template input-iterator Value_type range [first, last).<br> + * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>. + * <p> + * Throws jau::IllegalArgumentException() if <code>_capacity < Size_type(last - first)</code>. + * </p> + * @tparam InputIt template input-iterator custom type + * @param _capacity custom initial storage capacity + * @param first template input-iterator to first element of Value_type range [first, last) + * @param last template input-iterator to last element of Value_type range [first, last) + * @param growth_factor custom growth factor + * @param alloc custom Alloc_type instance + */ + template< class InputIt > + constexpr explicit darray(const Size_type _capacity, InputIt first, InputIt last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range_foreign(alloc_inst, _capacity, first, last) ), + end_(begin_ + Size_type(last - first) ), storage_end_( begin_ + _capacity ) + { } + + ~darray() noexcept { + clear(); + } + + // iterator + + constexpr iterator begin() noexcept { return begin_; } + + constexpr const_iterator begin() const noexcept { return begin_; } + + constexpr const_iterator cbegin() const noexcept { return begin_; } + + constexpr iterator end() noexcept { return end_; } + + constexpr const_iterator end() const noexcept { return end_; } + + constexpr const_iterator cend() const noexcept { return end_; } + +#if 0 + constexpr iterator storage_end() noexcept { return storage_end_; } + + constexpr const_iterator storage_end() const noexcept { return storage_end_; } + + constexpr const_iterator cstorage_end() const noexcept { return storage_end_; } +#endif + + // read access + + const Alloc_type& get_allocator_ref() const noexcept { + return alloc_inst; + } + + Alloc_type get_allocator() const noexcept { + return Alloc_type(alloc_inst); + } + + constexpr float growth_factor() const noexcept { + return growth_factor_; + } + + constexpr Size_type capacity() const noexcept { return Size_type(storage_end_ - begin_); } + + constexpr Size_type grow_number(const Size_type old_number ) const noexcept { + const Size_type res = static_cast<Size_type>(old_number * growth_factor_ + 0.5f); // simple round up + return std::max<Size_type>(old_number+1, res); + } + constexpr Size_type grow_capacity() const noexcept { + const Size_type old_number = capacity(); + const Size_type res = static_cast<Size_type>(old_number * growth_factor_ + 0.5f); // simple round up + return std::max<Size_type>(old_number+1, res); + } + + /** + * Like std::vector::empty(). + */ + constexpr bool empty() const noexcept { return begin_ == end_; } + + /** + * Returns true if capacity has been reached and the next push_back() + * will grow the storage and invalidates all iterators and references. + */ + constexpr bool capacity_reached() const noexcept { return end_ >= storage_end_; } + + /** + * Like std::vector::size(). + */ + constexpr Size_type size() const noexcept { return Size_type(end_ - begin_); } + + // mixed mutable/immutable element access + + /** + * Like std::vector::front(), mutable access. + */ + constexpr Value_type & front() { return *begin_; } + + /** + * Like std::vector::front(), immutable access. + */ + constexpr const Value_type & front() const { return *begin_; } + + /** + * Like std::vector::back(), mutable access. + */ + constexpr Value_type & back() { return *(end_-1); } + + /** + * Like std::vector::back(), immutable access. + */ + constexpr const Value_type & back() const { return *(end_-1); } + + /** + * Like std::vector::data(), const immutable pointer + */ + constexpr const Value_type* data() const noexcept { return begin_; } + + /** + * Like std::vector::data(), mutable pointer + */ + constexpr Value_type* data() noexcept { return begin_; } + + /** + * Like std::vector::operator[](Size_type), immutable reference. + */ + const Value_type & operator[](Size_type i) const noexcept { + return *(begin_+i); + } + + /** + * Like std::vector::operator[](Size_type), mutable reference. + */ + Value_type & operator[](Size_type i) noexcept { + return *(begin_+i); + } + + /** + * Like std::vector::at(Size_type), immutable reference. + */ + const Value_type & at(Size_type i) const { + if( 0 <= i && i < size() ) { + return *(begin_+i); + } + throw jau::IndexOutOfBoundsException(i, size(), E_FILE_LINE); + } + + /** + * Like std::vector::at(Size_type), mutable reference. + */ + Value_type & at(Size_type i) { + if( 0 <= i && i < size() ) { + return *(begin_+i); + } + throw jau::IndexOutOfBoundsException(i, size(), E_FILE_LINE); + } + + // write access, mutable array operations + + /** + * Like std::vector::reserve(), increases this instance's capacity to <code>new_capacity</code>. + * <p> + * Only creates a new storage and invalidates iterators if <code>new_capacity</code> + * is greater than the current jau::darray::capacity(). + * </p> + */ + void reserve(Size_type new_capacity) { + const Size_type capacity_ = capacity(); + if( new_capacity > capacity_ ) { + array_ref new_storage = allocStore(alloc_inst, new_capacity); + ctor_move_range(new_storage, begin_, end_); + + freeStore(alloc_inst, begin_, capacity_); + + set_iterator(new_storage, size(), new_capacity); + } + } + + /** + * Like std::vector::operator=(&), assignment + */ + darray& operator=(const darray& x) { + const Size_type size_ = size(); + const Size_type capacity_ = capacity(); + const Size_type x_size_ = x.size(); + dtor_range(begin_, end_); + if( x_size_ > capacity_ ) { + freeStore(alloc_inst, begin_, capacity_); + begin_ = clone_range(alloc_inst, x_size_, x.begin_, x.end_); + set_iterator(x_size_, x_size_); + } else { + ctor_copy_range(begin_, x.begin_, x.end_); + set_iterator(x_size_, capacity_); + } + return *this; + } + + /** + * Like std::vector::assign() + * @tparam InputIt foreign input-iterator to range of Value_type [first, last) + * @param first first foreign input-iterator to range of Value_type [first, last) + * @param last last foreign input-iterator to range of Value_type [first, last) + */ + template< class InputIt > + constexpr void assign( InputIt first, InputIt last ) { + const Size_type size_ = size(); + const Size_type capacity_ = capacity(); + const Size_type x_size_ = Size_type(last - first); + dtor_range(begin_, end_); + if( x_size_ > capacity_ ) { + freeStore(alloc_inst, begin_, capacity_); + begin_ = clone_range_foreign(alloc_inst, x_size_, first, last); + set_iterator(x_size_, x_size_); + } else { + ctor_copy_range_foreign(begin_, first, last); + set_iterator(x_size_, capacity_); + } + } + /** + * Like std::vector::assign(), but non-template overload using const_iterator. + * @param first first const_iterator to range of Value_type [first, last) + * @param last last const_iterator to range of Value_type [first, last) + */ + constexpr void assign( const_iterator first, const_iterator last ) { + const Size_type size_ = size(); + const Size_type capacity_ = capacity(); + const Size_type x_size_ = Size_type(last - first); + dtor_range(begin_, end_); + if( x_size_ > capacity_ ) { + freeStore(alloc_inst, begin_, capacity_); + begin_ = clone_range(alloc_inst, x_size_, first, last); + set_iterator(x_size_, x_size_); + } else { + ctor_copy_range(begin_, first, last); + set_iterator(x_size_, capacity_); + } + } + + /** + * Like std::vector::operator=(&&), move. + */ + darray& operator=(darray&& x) { + clear(); + alloc_inst = std::move(x.alloc_inst); + begin_ = std::move(x.begin_); + end_ = std::move(x.end_); + storage_end_ = std::move(x.storage_end_); + + // complete swapping store_ref + x.begin_ = nullptr; + x.end_ = nullptr; + x.storage_end_ = nullptr; + + return *this; + } + + /** + * Like std::vector::clear(), but ending with zero capacity. + */ + void clear() noexcept { + dtor_range(begin_, end_); + freeStore(alloc_inst, begin_, capacity()); + begin_ = nullptr; + end_ = nullptr; + storage_end_ = nullptr; + } + + /** + * Like std::vector::swap(). + */ + void swap(darray& x) noexcept { + std::swap(growth_factor_, x.growth_factor_); + std::swap(alloc_inst, x.alloc_inst); + std::swap(begin_, x.begin_); + std::swap(end_, x.end_); + std::swap(storage_end_, x.storage_end_); + } + + /** + * Like std::vector::pop_back(). + */ + void pop_back() noexcept { + if( begin_ != end_ ) { + ( --end_ )->~Value_type(); // placement new -> manual destruction! + } + } + + /** + * Like std::vector::push_back(), copy + * @param x the value to be added at the tail. + */ + void push_back(const Value_type& x) { + if( end_ == storage_end_ ) { + grow_storage_move(grow_capacity()); + } + new (end_) Value_type( x ); // placement new + ++end_; + } + + /** + * Like std::vector::push_back(), move + */ + void push_back(Value_type&& x) { + if( end_ == storage_end_ ) { + grow_storage_move(grow_capacity()); + } + new (end_) Value_type( std::move(x) ); // placement new + ++end_; + } + + /** + * Like std::vector::push_back(), but appends the whole Value_type range [first, last). + * @tparam InputIt foreign input-iterator to range of Value_type [first, last) + * @param first first foreign input-iterator to range of Value_type [first, last) + * @param last last foreign input-iterator to range of Value_type [first, last) + */ + template< class InputIt > + constexpr void push_back( InputIt first, InputIt last ) { + const Size_type count = Size_type(last - first); + + if( end_ + count >= storage_end_ ) { + grow_storage_move(size() + count); + } + ctor_copy_range_foreign(end_, first, last); + end_ += count; + } + + /** + * Like std::vector::push_back(), but appends the whole Value_type range [first, last). + * @param first first const_iterator to range of Value_type [first, last) + * @param last last const_iterator to range of Value_type [first, last) + */ + constexpr void push_back( const_iterator first, const_iterator last ) { + const Size_type count = Size_type(last - first); + + if( end_ + count >= storage_end_ ) { + grow_storage_move(size() + count); + } + ctor_copy_range(end_, first, last); + end_ += count; + } + + /** + * Like std::vector::erase(). + * <p> + * Removes the element at the given position + * and moves all subsequent elements one left. + * </p> + * <p> + * size will be reduced by one. + * </p> + * @param i the position of the element to be removed + */ + void erase(const Size_type i) { + const Size_type size_ = size(); + if( 0 <= i && i < size_ ) { + ( begin_ + i )->~Value_type(); // placement new -> manual destruction! + + const Size_type right_count = size_ - 1 - i; + if( 0 < right_count ) { + memmove(begin_+i, begin_+i+1, sizeof(Value_type)*right_count); // move right elems one left + } + --end_; + } else { + throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE); + } + } + + /** + * Like std::vector::erase(), removes the elements at pos. + * @return iterator following the last removed element. + */ + constexpr iterator erase (const_iterator pos) { + if( begin_ <= pos && pos < end_ ) { + ( pos )->~Value_type(); // placement new -> manual destruction! + const Size_type right_count = ( end_ - pos ) - 1; + if( 0 < right_count ) { + memmove(pos, pos+1, sizeof(Value_type)*right_count); // move right elems one left + } + --end_; + } + return begin_ <= pos && pos <= end_ ? pos : nullptr; + } + + /** + * Like std::vector::erase(), removes the elements in the range [first, last). + * @return iterator following the last removed element. + */ + constexpr iterator erase (const_iterator first, const_iterator last) { + const Size_type count = dtor_range(first, last); + if( count > 0 ) { + const Size_type right_count = ( end_ - last ) - 1; + if( 0 < right_count ) { + memmove(first, last, sizeof(Value_type)*right_count); // move right elems one left + } + end_ -= count; + } + return begin_ <= last && last <= end_ ? last : nullptr; + } + + /** + * Like std::vector::insert(), copy + * <p> + * Inserts the element at the given position + * and moves all elements from there to the right beforehand. + * </p> + * <p> + * size will be increased by one. + * </p> + * @param i the position of the element to be removed + */ + void insert(Size_type i, const Value_type& x) { + const Size_type size_ = size(); + if( 0 <= i && i <= size_ ) { + const Size_type old_capacity_ = capacity(); + if( size_ + 1 > old_capacity_ ) { + grow_storage_move(grow_number(old_capacity_)); + } + const Size_type right_count = size_ - i; + if( 0 < right_count ) { + memmove(begin_+i+1, begin_+i, sizeof(Value_type)*right_count); // move right elems one right + } + new (begin_+i) Value_type( x ); // placement new + ++end_; + } else { + throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE); + } + } + + /** + * Like std::vector::insert(), move + * <p> + * Inserts the element at the given position + * and moves all elements from there to the right beforehand. + * </p> + * <p> + * size will be increased by one. + * </p> + * @param i the position of the element to be removed + */ + void insert(Size_type i, Value_type&& x) { + const Size_type size_ = size(); + if( 0 <= i && i <= size_ ) { + const Size_type old_capacity_ = capacity(); + if( size_ + 1 > old_capacity_ ) { + grow_storage_move(grow_number(old_capacity_)); + } + const Size_type right_count = size_ - i; + if( 0 < right_count ) { + memmove(begin_+i+1, begin_+i, sizeof(Value_type)*right_count); // move right elems one right + } + new (begin_+i) Value_type( std::move(x) ); // placement new + ++end_; + } else { + throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE); + } + } + + /** + * Generic Value_type equal comparator to be user defined for e.g. jau::darray::push_back_unique(). + * @param a one element of the equality test. + * @param b the other element of the equality test. + * @return true if both are equal + */ + typedef bool(*equal_comparator)(const Value_type& a, const Value_type& b); + + /** + * Like std::vector::push_back(), but only if the newly added element does not yet exist. + * <p> + * Examples + * <pre> + * static jau::darray<Thing>::equal_comparator thingEqComparator = + * [](const Thing &a, const Thing &b) -> bool { return a == b; }; + * ... + * jau::darray<Thing> list; + * + * bool added = list.push_back_unique(new_element, thingEqComparator); + * ... + * darray<std::shared_ptr<Thing>> listOfRefs; + * bool added = listOfRefs.push_back_unique(new_element, + * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; }); + * </pre> + * </p> + * @param x the value to be added at the tail, if not existing yet. + * @param comparator the equal comparator to return true if both given elements are equal + * @return true if the element has been uniquely added, otherwise false + */ + bool push_back_unique(const Value_type& x, equal_comparator comparator) { + for(auto it = begin_; it != end_; ) { + if( comparator( *it, x ) ) { + return false; // already included + } else { + ++it; + } + } + push_back(x); + return true; + } + + /** + * Erase either the first matching element or all matching elements. + * <p> + * Examples + * <pre> + * darray<Thing> list; + * int count = list.erase_matching(element, true, + * [](const Thing &a, const Thing &b) -> bool { return a == b; }); + * ... + * static jau::darray<Thing>::equal_comparator thingRefEqComparator = + * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; }; + * ... + * darray<std::shared_ptr<Thing>> listOfRefs; + * int count = listOfRefs.erase_matching(element, false, thingRefEqComparator); + * </pre> + * </p> + * @param x the value to be added at the tail, if not existing yet. + * @param all_matching if true, erase all matching elements, otherwise only the first matching element. + * @param comparator the equal comparator to return true if both given elements are equal + * @return number of erased elements + */ + int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) { + int count = 0; + for(auto it = end_-1; begin_ <= it; --it) { + if( comparator( *it, x ) ) { + erase(it); + ++count; + if( !all_matching ) { + break; + } + } + } + return count; + } + }; +} /* namespace jau */ + +#endif /* JAU_DYN_ARRAY_HPP_ */ diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 33b448f..7bd76e5 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -21,7 +21,8 @@ set( SOURCES_IDIOMATIC_EXAMPLES test_lfringbuffer11.cpp test_mm_sc_drf_00.cpp test_mm_sc_drf_01.cpp - test_cowvector_perf01.cpp + test_cow_darray_01.cpp + test_cow_darray_perf01.cpp test_hashset_perf01.cpp ) diff --git a/test/test_cow_darray_01.cpp b/test/test_cow_darray_01.cpp new file mode 100644 index 0000000..6a1ce85 --- /dev/null +++ b/test/test_cow_darray_01.cpp @@ -0,0 +1,380 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright (c) 2020 Gothel Software e.K. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ +#include <iostream> +#include <cassert> +#include <cinttypes> +#include <cstring> +#include <random> +#include <vector> + +#define CATCH_CONFIG_RUNNER +// #define CATCH_CONFIG_MAIN +#include <catch2/catch_amalgamated.hpp> +#include <jau/test/catch2_ext.hpp> + +#include "test_datatype01.hpp" + +#include <jau/basic_types.hpp> +#include <jau/darray.hpp> +#include <jau/cow_darray.hpp> +#include <jau/cow_vector.hpp> +#include <jau/counting_allocator.hpp> + +using namespace jau; + +static uint8_t start_addr_b[] = {0x20, 0x26, 0x2A, 0x01, 0x20, 0x10}; +static Addr48Bit start_addr(start_addr_b); + +typedef std::vector<DataType01, counting_allocator<DataType01>> DataType01Vector; + +template<class T> +DataType01 * findDataSet01_idx(T& data, DataType01 const & elem) noexcept { + const size_t size = data.size(); + for (size_t i = 0; i < size; i++) { + DataType01 & e = data[i]; + if ( elem == e ) { + return &e; + } + } + return nullptr; +} +template<class T> +const DataType01 * findDataSet01_itr(T& data, DataType01 const & elem) noexcept { + typename T::const_iterator iter = data.cbegin(); + typename T::const_iterator end = data.cend(); + for(; iter != end ; ++iter) { + if( elem == *iter ) { + return &(*iter); + } + } + return nullptr; +} + +template<class T> +static void test_00_list_idx(T& data, const bool show) { + Addr48Bit a0(start_addr); + const std::size_t size = data.size(); + for (std::size_t i = 0; i < size && a0.next(); ++i) { + const DataType01 & e = data[i]; + e.nop(); + if( show ) { + printf("data[%zu]: %s\n", i, e.toString().c_str()); + } + REQUIRE(e.address == a0); + } +} +template<class T> +static void test_00_list_itr(T& data, const bool show) { + Addr48Bit a0(start_addr); + typename T::const_iterator iter = data.cbegin(); + typename T::const_iterator end = data.cend(); + for(std::size_t i = 0; iter != end && a0.next(); ++iter, ++i) { + const DataType01 & e = *iter; + e.nop(); + if( show ) { + printf("data[%zu]: %s\n", i, e.toString().c_str()); + } + REQUIRE(e.address == a0); + } +} + +template<class T> +static void test_00_seq_find_idx(T& data) { + Addr48Bit a0(start_addr); + const std::size_t size = data.size(); + std::size_t fi = 0, i=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + DataType01 *found = findDataSet01_idx(data, elem); + if( nullptr != found ) { + fi++; + found->nop(); + } + } + REQUIRE(fi == i); +} +template<class T> +static void test_00_seq_find_itr(T& data) { + Addr48Bit a0(start_addr); + const std::size_t size = data.size(); + std::size_t fi = 0, i=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + const DataType01 *found = findDataSet01_itr(data, elem); + if( nullptr != found ) { + fi++; + found->nop(); + } + } + REQUIRE(fi == i); +} + +template<class T> +static void test_00_seq_fill(T& data, const std::size_t size) { + Addr48Bit a0(start_addr); + std::size_t i=0; + + for(; i<size && a0.next(); i++) { + data.push_back( std::move( DataType01(a0, static_cast<uint8_t>(1)) ) ); + } + if( i != data.size() ) { + test_00_list_itr(data, true); + printf("a0 %s\n", a0.toString().c_str()); + printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i); + } + REQUIRE(i == data.size()); +} + +template<class T> +static void test_00_seq_fill_unique_idx(T& data, const std::size_t size) { + Addr48Bit a0(start_addr); + std::size_t i=0, fi=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + DataType01* exist = findDataSet01_idx(data, elem); + if( nullptr == exist ) { + data.push_back( std::move(elem) ); + fi++; + } else { + printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist)); + } + } + if( fi != size ) { + test_00_list_idx(data, true); + printf("a0 %s\n", a0.toString().c_str()); + printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i); + } + REQUIRE(i == data.size()); + REQUIRE(fi == size); +} +template<class T> +static void test_00_seq_fill_unique_itr(T& data, const std::size_t size) { + Addr48Bit a0(start_addr); + std::size_t i=0, fi=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + const DataType01* exist = findDataSet01_itr(data, elem); + if( nullptr == exist ) { + data.push_back( std::move(elem) ); + fi++; + } else { + printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist)); + } + } + if( fi != size ) { + test_00_list_itr(data, true); + printf("a0 %s\n", a0.toString().c_str()); + printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i); + } + REQUIRE(i == data.size()); + REQUIRE(fi == size); +} + +/**************************************************************************************** + ****************************************************************************************/ + +template<class T> +static bool test_01_seq_fill_list_idx(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) { + (void)type_id; + + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_list_idx(data, false); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + data.clear(); + REQUIRE(data.size() == 0); + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} +template<class T> +static bool test_01_seq_fill_list_itr(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) { + (void)type_id; + + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_list_itr(data, false); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + data.clear(); + REQUIRE(data.size() == 0); + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +template<class T> +static bool test_02_seq_fillunique_find_idx(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) { + (void)type_id; + + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill_unique_idx(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_seq_find_idx(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + data.clear(); + REQUIRE(data.size() == 0); + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} +template<class T> +static bool test_02_seq_fillunique_find_itr(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) { + (void)type_id; + + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill_unique_itr(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_seq_find_itr(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + data.clear(); + REQUIRE(data.size() == 0); + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +/**************************************************************************************** + ****************************************************************************************/ + +TEST_CASE( "STD Vector Test 01 - Fill Sequential and List", "[datatype][std][vector]" ) { + test_01_seq_fill_list_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_empty__", 100, 0); + test_01_seq_fill_list_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_reserve", 100, 100); + + test_01_seq_fill_list_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_empty__", 100, 0); + test_01_seq_fill_list_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_reserve", 100, 100); +} + +TEST_CASE( "STD Vector Test 02 - Fill Unique and Find-Each", "[datatype][std][vector]" ) { + test_02_seq_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_reserve", 100, 100); + + test_02_seq_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_reserve", 100, 100); +} + +TEST_CASE( "JAU COW_Vector Test 11 - Fill Sequential and List", "[datatype][jau][cow_vector]" ) { + // test_01_seq_fill_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_empty__", 100, 0); + // test_01_seq_fill_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_reserve", 100, 100); + + test_01_seq_fill_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_empty__", 100, 0); + test_01_seq_fill_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_reserve", 100, 100); +} + +TEST_CASE( "JAU COW_Vector Test 12 - Fill Unique and Find-Each", "[datatype][jau][cow_vector]" ) { + // test_02_seq_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_empty__", 100, 0); + // test_02_seq_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_reserve", 100, 100); + + test_02_seq_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_reserve", 100, 100); +} + +TEST_CASE( "JAU DArray Test 21 - Fill Sequential and List", "[datatype][jau][darray]" ) { + test_01_seq_fill_list_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_empty__", 100, 0); + test_01_seq_fill_list_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_reserve", 100, 100); + + test_01_seq_fill_list_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_empty__", 100, 0); + test_01_seq_fill_list_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_reserve", 100, 100); +} + +TEST_CASE( "JAU DArray Test 22 - Fill Unique and Find-Each", "[datatype][jau][darray]" ) { + test_02_seq_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_reserve", 100, 100); + + test_02_seq_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_reserve", 100, 100); +} + +TEST_CASE( "JAU COW_DArray Test 31 - Fill Sequential and List", "[datatype][jau][cow_darray]" ) { + // test_01_seq_fill_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_empty__", 100, 0); + // test_01_seq_fill_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_reserve", 100, 100); + + test_01_seq_fill_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_empty__", 100, 0); + test_01_seq_fill_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_reserve", 100, 100); +} + +TEST_CASE( "JAU COW_DArray Test 32 - Fill Unique and Find-Each", "[datatype][jau][cow_darray]" ) { + // test_02_seq_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_empty__", 100, 0); + // test_02_seq_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_reserve", 100, 100); + + test_02_seq_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_empty__", 100, 0); + test_02_seq_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_reserve", 100, 100); +} diff --git a/test/test_cow_darray_perf01.cpp b/test/test_cow_darray_perf01.cpp new file mode 100644 index 0000000..6223395 --- /dev/null +++ b/test/test_cow_darray_perf01.cpp @@ -0,0 +1,565 @@ +/* + * Author: Sven Gothel <[email protected]> + * Copyright (c) 2020 Gothel Software e.K. + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE + * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION + * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION + * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ +#include <iostream> +#include <cassert> +#include <cinttypes> +#include <cstring> +#include <random> +#include <vector> + +#define CATCH_CONFIG_RUNNER +// #define CATCH_CONFIG_MAIN +#include <catch2/catch_amalgamated.hpp> +#include <jau/test/catch2_ext.hpp> + +#include "test_datatype01.hpp" + +#include <jau/basic_types.hpp> +#include <jau/darray.hpp> +#include <jau/cow_darray.hpp> +#include <jau/cow_vector.hpp> +#include <jau/counting_allocator.hpp> + +using namespace jau; + +static uint8_t start_addr_b[] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; +static Addr48Bit start_addr(start_addr_b); + +/**************************************************************************************** + ****************************************************************************************/ + +template<class T, typename Size_type> +DataType01 * findDataSet01_idx(T& data, DataType01 const & elem) noexcept { + const Size_type size = data.size(); + for (Size_type i = 0; i < size; i++) { + DataType01 & e = data[i]; + if ( elem == e ) { + return &e; + } + } + return nullptr; +} + +template<class T> +const DataType01 * findDataSet01_itr(T& data, DataType01 const & elem) noexcept { + typename T::const_iterator iter = data.cbegin(); + typename T::const_iterator end = data.cend(); + for(; iter != end ; ++iter) { + if( elem == *iter ) { + return &(*iter); + } + } + return nullptr; +} + +template<class T, typename Size_type> +static void test_00_list_idx(T& data) { + const Size_type size = data.size(); + for (Size_type i = 0; i < size; i++) { + const DataType01 & e = data[i]; + e.nop(); + } +} + +template<class T> +static void test_00_list_itr(T& data) { + typename T::const_iterator iter = data.cbegin(); + typename T::const_iterator end = data.cend(); + for(; iter != end ; ++iter) { + const DataType01 & e = *iter; + e.nop(); + } +} + +template<class T, typename Size_type> +static void test_00_seq_find_idx(T& data) { + Addr48Bit a0(start_addr); + const Size_type size = data.size(); + Size_type fi = 0, i=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + DataType01 *found = findDataSet01_idx<T, Size_type>(data, elem); + if( nullptr != found ) { + fi++; + found->nop(); + } + } + REQUIRE(fi == i); +} + +template<class T, typename Size_type> +static void test_00_seq_find_itr(T& data) { + Addr48Bit a0(start_addr); + const Size_type size = data.size(); + Size_type fi = 0, i=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + const DataType01 *found = findDataSet01_itr<T>(data, elem); + if( nullptr != found ) { + fi++; + found->nop(); + } + } + REQUIRE(fi == i); +} + +template<class T, typename Size_type> +static void test_00_seq_fill(T& data, const Size_type size) { + Addr48Bit a0(start_addr); + Size_type i=0; + + for(; i<size && a0.next(); i++) { + data.push_back( std::move( DataType01(a0, static_cast<uint8_t>(1)) ) ); + } + REQUIRE(i == data.size()); +} + +template<class T, typename Size_type> +static void test_00_seq_fill_unique_idx(T& data, const Size_type size) { + Addr48Bit a0(start_addr); + Size_type i=0, fi=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + DataType01* exist = findDataSet01_idx<T, Size_type>(data, elem); + if( nullptr == exist ) { + data.push_back( std::move(elem) ); + fi++; + } + } + REQUIRE(i == data.size()); + REQUIRE(fi == size); +} +template<class T, typename Size_type> +static void test_00_seq_fill_unique_itr(T& data, const Size_type size) { + Addr48Bit a0(start_addr); + Size_type i=0, fi=0; + + for(; i<size && a0.next(); i++) { + DataType01 elem(a0, static_cast<uint8_t>(1)); + const DataType01* exist = findDataSet01_itr<T>(data, elem); + if( nullptr == exist ) { + data.push_back( std::move(elem) ); + fi++; + } + } + REQUIRE(i == data.size()); + REQUIRE(fi == size); +} + +template<class T> +static void print_mem(const std::string& pre, const T& data) { + std::size_t bytes_element = sizeof(DataType01); + std::size_t elements = data.size(); + std::size_t bytes_net = elements * bytes_element; + std::size_t bytes_total = data.get_allocator().memory_usage; + double overhead = 0 == bytes_total ? 0.0 : ( 0 == bytes_net ? 10.0 : (double)bytes_total / (double)bytes_net ); + printf("Mem: %s: Elements %s x %zu bytes; %s, %lf ratio\n", + pre.c_str(), int64DecString(elements, ',', 5).c_str(), + bytes_element, data.get_allocator().toString(10, 5).c_str(), overhead); + // 5: 1,000 + // 7: 100,000 + // 9: 1,000,000 +} + +/**************************************************************************************** + ****************************************************************************************/ + +template<class T, typename Size_type> +static bool test_01_seq_fill_list_idx(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) { + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 01 (empty)", data); } + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill<T, Size_type>(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_list_idx<T, Size_type>(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + if( do_print_mem ) { print_mem(type_id+" 01 (full_)", data); } + + data.clear(); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 01 (clear)", data); } + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +template<class T, typename Size_type> +static bool test_01_seq_fill_list_itr(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) { + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 01 (empty)", data); } + + if( 0 < reserve0 ) { + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + } + + test_00_seq_fill<T, Size_type>(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_list_itr<T>(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + if( do_print_mem ) { print_mem(type_id+" 01 (full_)", data); } + + data.clear(); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 01 (clear)", data); } + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +template<class T, typename Size_type> +static bool test_02_seq_fillunique_find_idx(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) { + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); } + + if( 0 < reserve0 ) { + data.reserve(reserve0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == reserve0); + } + + test_00_seq_fill_unique_idx<T, Size_type>(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_seq_find_idx<T, Size_type>(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); } + + data.clear(); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); } + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} +template<class T, typename Size_type> +static bool test_02_seq_fillunique_find_itr(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) { + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); } + + if( 0 < reserve0 ) { + data.reserve(reserve0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == reserve0); + } + + test_00_seq_fill_unique_itr<T, Size_type>(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_seq_find_itr<T, Size_type>(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); } + + data.clear(); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); } + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +template<class T, typename Size_type> +static bool test_02b_seq_fillunique_find_itr_rserv(const std::string& type_id, const Size_type size0, const bool do_print_mem) { + T data; + REQUIRE(0 == data.get_allocator().memory_usage); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); } + + data.reserve(size0); + REQUIRE(data.size() == 0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.capacity() == size0); + + test_00_seq_fill_unique_itr<T, Size_type>(data, size0); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + + test_00_seq_find_itr<T, Size_type>(data); + REQUIRE(0 != data.get_allocator().memory_usage); + REQUIRE(data.size() == size0); + if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); } + + data.clear(); + REQUIRE(data.size() == 0); + // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); } + // REQUIRE(0 == data.get_allocator().memory_usage); + return data.size() == 0; +} + +/**************************************************************************************** + ****************************************************************************************/ + +template<class T, typename Size_type> +static bool footprint_fillseq_list_itr(const std::string& type_id, const bool do_rserv) { + // test_01_seq_fill_list_itr<T, Size_type>(type_id, 25, do_rserv? 25 : 0, true); + test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, true); + if( !catch_auto_run ) { + test_01_seq_fill_list_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, true); + test_01_seq_fill_list_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, true); + } + return true; +} + +template<class T, typename Size_type> +static bool benchmark_fillseq_list_idx(const std::string& title_pre, const std::string& type_id, + const bool do_rserv) { + if( catch_perf_analysis ) { + test_01_seq_fill_list_idx<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false); + return true; + } + if( catch_auto_run ) { + test_01_seq_fill_list_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + return true; + } + // BENCHMARK(title_pre+" FillSeq_List 25") { + // return test_01_seq_fill_list_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false); + // }; + BENCHMARK(title_pre+" FillSeq_List 50") { + return test_01_seq_fill_list_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + }; + BENCHMARK(title_pre+" FillSeq_List 100") { + return test_01_seq_fill_list_idx<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false); + }; + BENCHMARK(title_pre+" FillSeq_List 1000") { + return test_01_seq_fill_list_idx<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false); + }; + return true; +} +template<class T, typename Size_type> +static bool benchmark_fillseq_list_itr(const std::string& title_pre, const std::string& type_id, + const bool do_rserv) { + if( catch_perf_analysis ) { + test_01_seq_fill_list_itr<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false); + return true; + } + if( catch_auto_run ) { + test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + return true; + } + // BENCHMARK(title_pre+" FillSeq_List 25") { + // return test_01_seq_fill_list_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false); + // }; + BENCHMARK(title_pre+" FillSeq_List 50") { + return test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + }; + BENCHMARK(title_pre+" FillSeq_List 100") { + return test_01_seq_fill_list_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false); + }; + BENCHMARK(title_pre+" FillSeq_List 1000") { + return test_01_seq_fill_list_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false); + }; + return true; +} + +template<class T, typename Size_type> +static bool benchmark_fillunique_find_idx(const std::string& title_pre, const std::string& type_id, + const bool do_rserv) { + if( catch_perf_analysis ) { + test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false); + return true; + } + if( catch_auto_run ) { + test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + return true; + } + // BENCHMARK(title_pre+" FillUni_List 25") { + // return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false); + // }; + BENCHMARK(title_pre+" FillUni_List 50") { + return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + }; + BENCHMARK(title_pre+" FillUni_List 100") { + return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false); + }; + BENCHMARK(title_pre+" FillUni_List 1000") { + return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false); + }; + return true; +} +template<class T, typename Size_type> +static bool benchmark_fillunique_find_itr(const std::string& title_pre, const std::string& type_id, + const bool do_rserv) { + if( catch_perf_analysis ) { + BENCHMARK(title_pre+" FillUni_List 1000") { + return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false); + }; + // test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false); + return true; + } + if( catch_auto_run ) { + test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + return true; + } + // BENCHMARK(title_pre+" FillUni_List 25") { + // return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false); + // }; + BENCHMARK(title_pre+" FillUni_List 50") { + return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false); + }; + BENCHMARK(title_pre+" FillUni_List 100") { + return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false); + }; + BENCHMARK(title_pre+" FillUni_List 1000") { + return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false); + }; + return true; +} +template<class T, typename Size_type> +static bool benchmark_fillunique_find_itr_rserv(const std::string& title_pre, const std::string& type_id) { + if( catch_perf_analysis ) { + BENCHMARK(title_pre+" FillUni_List 1000") { + return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 1000, false); + }; + // test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 100000, false); + return true; + } + if( catch_auto_run ) { + test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 50, false); + return true; + } + // BENCHMARK(title_pre+" FillUni_List 25") { + // return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 25, false); + // }; + BENCHMARK(title_pre+" FillUni_List 50") { + return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 50, false); + }; + BENCHMARK(title_pre+" FillUni_List 100") { + return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 100, false); + }; + BENCHMARK(title_pre+" FillUni_List 1000") { + return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 1000, false); + }; + return true; +} + +/**************************************************************************************** + ****************************************************************************************/ + +TEST_CASE( "Memory Footprint 01 - Fill Sequential and List", "[datatype][footprint]" ) { + if( catch_perf_analysis ) { + return; + } + footprint_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("stdvec_empty_", false); + footprint_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("darray_empty_", false); + footprint_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("cowstdvec_empty_", false); + footprint_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("cowdarray_empty_", false); + +#if 0 + footprint_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("stdvec_rserv", true); + footprint_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("darray_rserv", true); + footprint_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("cowstdvec_rserv", true); + footprint_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("cowdarray_rserv", true); +#endif +} + +TEST_CASE( "Perf Test 01 - Fill Sequential and List, empty and reserve", "[datatype][sequential]" ) { + if( catch_perf_analysis ) { +#if 0 + benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false); + benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>, jau::nsize_t>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false); +#endif + return; + } + benchmark_fillseq_list_idx< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_idx", "stdvec_empty_", false); + benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false); + + benchmark_fillseq_list_idx< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_idx", "darray_empty_", false); + benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>, jau::nsize_t>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false); + + // benchmark_fillseq_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_idx", "cowstdvec_empty_", false); + benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false); + + // benchmark_fillseq_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_idx", "cowdarray_empty_", false); + benchmark_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_itr", "cowdarray_empty_", false); + + benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_rserv_itr", "stdvec_rserv", true); + benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_rserv_itr", "darray_rserv", true); + benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv", true); + benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv", true); +} + +TEST_CASE( "Perf Test 02 - Fill Unique and List, empty and reserve", "[datatype][unique]" ) { + if( catch_perf_analysis ) { +#if 1 + // benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false); + // benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_empty_itr", "cowdarray_empty_", false); + + benchmark_fillunique_find_itr_rserv< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv_"); + benchmark_fillunique_find_itr_rserv< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_rserv_itr", "cowdarray_rserv_"); + + benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false); + benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_empty_itr", "cowdarray_empty_", false); + +#endif + return; + } + benchmark_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_idx", "stdvec_empty_", false); + + benchmark_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false); + + benchmark_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_idx", "darray_empty_", false); + benchmark_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false); + + // benchmark_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_idx", "cowstdvec_empty_", false); + benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false); + + // benchmark_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_idx", "cowdarray_empty_", false); + benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_itr", "cowdarray_empty_", false); + +#if 1 + benchmark_fillunique_find_itr_rserv< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_rserv_itr", "stdvec_rserv"); + benchmark_fillunique_find_itr_rserv< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_rserv_itr", "darray_rserv"); + benchmark_fillunique_find_itr_rserv< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv"); + benchmark_fillunique_find_itr_rserv< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_rserv_itr", "cowdarray_rserv"); +#endif +} + diff --git a/test/test_cowvector_perf01.cpp b/test/test_cowvector_perf01.cpp deleted file mode 100644 index b20520f..0000000 --- a/test/test_cowvector_perf01.cpp +++ /dev/null @@ -1,340 +0,0 @@ -/* - * Author: Sven Gothel <[email protected]> - * Copyright (c) 2020 Gothel Software e.K. - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - */ -#include <iostream> -#include <cassert> -#include <cinttypes> -#include <cstring> -#include <random> -#include <vector> - -#define CATCH_CONFIG_RUNNER -// #define CATCH_CONFIG_MAIN -#include <catch2/catch_amalgamated.hpp> -#include <jau/test/catch2_ext.hpp> - -#include "test_datatype01.hpp" - -#include <jau/basic_types.hpp> -#include <jau/cow_vector.hpp> -#include <jau/counting_allocator.hpp> - -using namespace jau; - -static uint8_t start_addr_b[] = {0x20, 0x26, 0x2A, 0x01, 0x20, 0x10}; -static Addr48Bit start_addr(start_addr_b); - -typedef std::vector<DataType01, counting_allocator<DataType01>> DataType01Vector; - -template<class T> -DataType01 * findDataSet01(T& data, DataType01 const & elem) noexcept { - const size_t size = data.size(); - for (size_t i = 0; i < size; i++) { - DataType01 & e = data[i]; - if ( elem == e ) { - return &e; - } - } - return nullptr; -} - -template<class T> -static void test_00_list(T& data, const bool show) { - const std::size_t size = data.size(); - for (std::size_t i = 0; i < size; i++) { - DataType01 & e = data[i]; - e.nop(); - if( show ) { - printf("data[%zu]: %s\n", i, e.toString().c_str()); - } - } -} - -template<class T> -static void test_00_seq_find_each(T& data, const bool show) { - Addr48Bit a0(start_addr); - const std::size_t size = data.size(); - std::size_t fi = 0, i=0; - - for(; i<size && a0.next(); i++) { - DataType01 elem(a0, static_cast<uint8_t>(1)); - DataType01 *found = findDataSet01(data, elem); - if( nullptr != found ) { - fi++; - found->nop(); - if( show ) { - printf("data[%zu, %zu]: %s\n", i, fi, found->toString().c_str()); - } - } - } - REQUIRE(fi == i); -} - -template<class T> -static void test_00_seq_fill(T& data, const std::size_t size) { - // data.reserve(size); - Addr48Bit a0(start_addr); - std::size_t i=0; - - for(; i<size && a0.next(); i++) { - DataType01 elem(a0, static_cast<uint8_t>(1)); - data.push_back( elem ); - } - if( i != data.size() ) { - test_00_list(data, true); - printf("a0 %s\n", a0.toString().c_str()); - printf("Size %zu, expected %zu, iter %zu\n", data.size(), size, i); - } - REQUIRE(i == data.size()); -} - -template<class T> -static void test_00_seq_fill_unique(T& data, const std::size_t size) { - // data.reserve(size); - Addr48Bit a0(start_addr); - std::size_t i=0, fi=0; - - for(; i<size && a0.next(); i++) { - DataType01 elem(a0, static_cast<uint8_t>(1)); - DataType01* exist = findDataSet01(data, elem); - if( nullptr == exist ) { - data.push_back(elem); - fi++; - } else { - printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist)); - } - } - if( fi != size ) { - test_00_list(data, true); - printf("a0 %s\n", a0.toString().c_str()); - printf("Size %zu, expected %zu, iter %zu\n", data.size(), size, i); - } - REQUIRE(i == data.size()); - REQUIRE(fi == size); -} - -template<class T> -static void print_mem(const std::string& pre, const T& data) { - std::size_t bytes_element = sizeof(DataType01); - std::size_t elements = data.size(); - std::size_t bytes_net = elements * bytes_element; - std::size_t bytes_total = data.get_allocator().memory_usage; - double overhead = 0 == bytes_total ? 0.0 : ( 0 == bytes_net ? 10.0 : (double)bytes_total / (double)bytes_net ); - printf("Mem: %s: Elements %s x %zu bytes; %s, %lf ratio\n", - pre.c_str(), int64DecString(elements, ',', 5).c_str(), - bytes_element, data.get_allocator().toString(10, 5).c_str(), overhead); - // 5: 1,000 - // 7: 100,000 - // 9: 1,000,000 -} - -static bool test_stdvec_01_seq_fill_list_clear(const std::size_t size0, const bool do_print_mem) { - std::vector<DataType01, counting_allocator<DataType01>> data; - REQUIRE(0 == data.get_allocator().memory_usage); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("stdvec_01 (empty)", data); } - - test_00_seq_fill(data, size0); - REQUIRE(data.size() == size0); - - test_00_list(data, false); - REQUIRE(data.size() == size0); - if( do_print_mem ) { print_mem("stdvec_01 (full_)", data); } - - data.clear(); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("stdvec_01 (clear)", data); } - // REQUIRE(0 == data.get_allocator().memory_usage); - return data.size() == 0; -} - -static bool test_stdvec_02_seq_fillunique_findeach_clear(const std::size_t size0, const bool do_print_mem) { - std::vector<DataType01, counting_allocator<DataType01>> data; - REQUIRE(0 == data.get_allocator().memory_usage); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("stdvec_02 (empty)", data); } - - test_00_seq_fill_unique(data, size0); - REQUIRE(data.size() == size0); - - test_00_seq_find_each(data, false); - REQUIRE(data.size() == size0); - if( do_print_mem ) { print_mem("stdvec_02 (full_)", data); } - - data.clear(); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("stdvec_02 (clear)", data); } - // REQUIRE(0 == data.get_allocator().memory_usage); - return data.size() == 0; -} - -static bool test_cowvec_11_seq_fill_list_clear(const std::size_t size0, const bool do_print_mem) { - jau::cow_vector<DataType01, counting_allocator<DataType01>> data; - REQUIRE(0 == data.get_allocator().memory_usage); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("cowvec_11 (empty)", data); } - - test_00_seq_fill(data, size0); - REQUIRE(data.size() == size0); - if( do_print_mem ) { print_mem("cowvec_11 (full_)", data); } - - test_00_list(data, false); - REQUIRE(data.size() == size0); - - data.clear(); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("cowvec_11 (clear)", data); } - // REQUIRE(0 == data.get_allocator().memory_usage); - return data.size() == 0; -} - -static bool test_cowvec_12_seq_fillunique_findeach_clear(const std::size_t size0, const bool do_print_mem) { - jau::cow_vector<DataType01, counting_allocator<DataType01>> data; - REQUIRE(0 == data.get_allocator().memory_usage); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("cowvec_12 (empty)", data); } - - test_00_seq_fill_unique(data, size0); - REQUIRE(data.size() == size0); - if( do_print_mem ) { print_mem("cowvec_12 (full_)", data); } - - test_00_seq_find_each(data, false); - REQUIRE(data.size() == size0); - - data.clear(); - REQUIRE(data.size() == 0); - // if( do_print_mem ) { print_mem("cowvec_12 (clear)", data); } - // REQUIRE(0 == data.get_allocator().memory_usage); - return data.size() == 0; -} - -TEST_CASE( "STD Vector Perf Test 01 - Fill Sequential and List", "[datatype][std][vector]" ) { - test_stdvec_01_seq_fill_list_clear(25, true); - test_stdvec_01_seq_fill_list_clear(50, true); - if( !catch_auto_run ) { - test_stdvec_01_seq_fill_list_clear(100, true); - test_stdvec_01_seq_fill_list_clear(200, true); - test_stdvec_01_seq_fill_list_clear(1000, true); - } - - BENCHMARK("Seq_List 25") { - return test_stdvec_01_seq_fill_list_clear(25, false); - }; - BENCHMARK("Seq_List 50") { - return test_stdvec_01_seq_fill_list_clear(50, false); - }; - if( !catch_auto_run ) { - BENCHMARK("Seq_List 100") { - return test_stdvec_01_seq_fill_list_clear(100, false); - }; - BENCHMARK("Seq_List 200") { - return test_stdvec_01_seq_fill_list_clear(200, false); - }; - BENCHMARK("Seq_List 1000") { - return test_stdvec_01_seq_fill_list_clear(1000, false); - }; - } -} -TEST_CASE( "COW Vector Perf Test 11 - Fill Sequential and List", "[datatype][cow][vector]" ) { - test_cowvec_11_seq_fill_list_clear(25, true); - test_cowvec_11_seq_fill_list_clear(50, true); - if( !catch_auto_run ) { - test_cowvec_11_seq_fill_list_clear(100, true); - test_cowvec_11_seq_fill_list_clear(200, true); - test_cowvec_11_seq_fill_list_clear(1000, true); - } - - BENCHMARK("Seq_List 25") { - return test_cowvec_11_seq_fill_list_clear(25, false); - }; - BENCHMARK("Seq_List 50") { - return test_cowvec_11_seq_fill_list_clear(50, false); - }; - if( !catch_auto_run ) { - BENCHMARK("Seq_List 100") { - return test_cowvec_11_seq_fill_list_clear(100, false); - }; - BENCHMARK("Seq_List 200") { - return test_cowvec_11_seq_fill_list_clear(200, false); - }; - BENCHMARK("Seq_List 1000") { - return test_cowvec_11_seq_fill_list_clear(1000, false); - }; - } -} - -TEST_CASE( "STD Vector Perf Test 02 - Fill Unique and Find-Each", "[datatype][std][vector]" ) { - test_stdvec_02_seq_fillunique_findeach_clear(25, true); - test_stdvec_02_seq_fillunique_findeach_clear(50, true); - if( !catch_auto_run ) { - test_stdvec_02_seq_fillunique_findeach_clear(100, true); - test_stdvec_02_seq_fillunique_findeach_clear(200, true); - test_stdvec_02_seq_fillunique_findeach_clear(1000, true); - } - - BENCHMARK("Unique Find 25") { - return test_stdvec_02_seq_fillunique_findeach_clear(25, false); - }; - BENCHMARK("Unique Find 50") { - return test_stdvec_02_seq_fillunique_findeach_clear(50, false); - }; - if( !catch_auto_run ) { - BENCHMARK("Unique Find 100") { - return test_stdvec_02_seq_fillunique_findeach_clear(100, false); - }; - BENCHMARK("Unique Find 200") { - return test_stdvec_02_seq_fillunique_findeach_clear(200, false); - }; - BENCHMARK("Unique Find 1000") { - return test_stdvec_02_seq_fillunique_findeach_clear(1000, false); - }; - } -} -TEST_CASE( "COW Vector Perf Test 12 - Fill Unique and Find-Each", "[datatype][cow][vector]" ) { - test_cowvec_12_seq_fillunique_findeach_clear(25, true); - test_cowvec_12_seq_fillunique_findeach_clear(50, true); - if( !catch_auto_run ) { - test_cowvec_12_seq_fillunique_findeach_clear(100, true); - test_cowvec_12_seq_fillunique_findeach_clear(200, true); - test_cowvec_12_seq_fillunique_findeach_clear(1000, true); - } - - BENCHMARK("Unique Find 25") { - return test_cowvec_12_seq_fillunique_findeach_clear(25, false); - }; - BENCHMARK("Unique Find 50") { - return test_cowvec_12_seq_fillunique_findeach_clear(50, false); - }; - if( !catch_auto_run ) { - BENCHMARK("Unique Find 100") { - return test_cowvec_12_seq_fillunique_findeach_clear(100, false); - }; - BENCHMARK("Unique Find 200") { - return test_cowvec_12_seq_fillunique_findeach_clear(200, false); - }; - BENCHMARK("Unique Find 1000") { - return test_cowvec_12_seq_fillunique_findeach_clear(1000, false); - }; - } -} - |