Line data    Source code

       1             : /******************************************************************************
       2             :  * Project:  GDAL Core
       3             :  * Purpose:  Test performance of gdal_minmax_element.hpp
       4             :  * Author:   Even Rouault, <even dot rouault at spatialys.com>
       5             :  *
       6             :  ******************************************************************************
       7             :  * Copyright (c) 2024, Even Rouault <even dot rouault at spatialys.com>
       8             :  *
       9             :  * SPDX-License-Identifier: MIT
      10             :  ****************************************************************************/
      11             : 
      12             : #include "gdal_minmax_element.hpp"
      13             : 
      14             : #include <chrono>
      15             : #include <random>
      16             : 
      17          10 : template <class T> void randomFill(T *v, size_t size, bool withNaN = true)
      18             : {
      19          20 :     std::random_device rd;
      20          10 :     std::mt19937 gen{rd()};
      21          10 :     std::normal_distribution<> dist{127, 30};
      22   100000000 :     for (size_t i = 0; i < size; i++)
      23             :     {
      24   100000000 :         v[i] = static_cast<T>(dist(gen));
      25             :         if constexpr (std::is_same<T, float>::value ||
      26             :                       std::is_same<T, double>::value)
      27             :         {
      28    40000000 :             if (withNaN && (i == 0 || (i > 10 && ((i + 1) % 1024) <= 4)))
      29       97652 :                 v[i] = std::numeric_limits<float>::quiet_NaN();
      30             :         }
      31             :     }
      32          10 : }
      33             : 
      34             : constexpr size_t SIZE = 10 * 1000 * 1000 + 1;
      35             : constexpr int N_ITERS = 1;
      36             : 
      37             : template <class T>
      38             : #if defined(__GNUC__)
      39             : __attribute__((noinline))
      40             : #endif
      41             : static void
      42           6 : benchIntegers(GDALDataType eDT, T noData)
      43             : {
      44           6 :     std::vector<T> x;
      45           6 :     x.resize(SIZE);
      46           6 :     randomFill(x.data(), x.size());
      47             :     {
      48           6 :         auto start = std::chrono::steady_clock::now();
      49           6 :         int idx = 0;
      50          12 :         for (int i = 0; i < N_ITERS; ++i)
      51             :         {
      52           6 :             idx += static_cast<int>(
      53           6 :                 gdal::min_element(x.data(), x.size(), eDT, false, 0));
      54             :         }
      55           6 :         idx /= N_ITERS;
      56           6 :         printf("min at idx %d (optimized)\n", idx);
      57           6 :         auto end = std::chrono::steady_clock::now();
      58           6 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
      59             :     }
      60             :     {
      61           6 :         auto start = std::chrono::steady_clock::now();
      62           6 :         int idx = 0;
      63          12 :         for (int i = 0; i < N_ITERS; ++i)
      64             :         {
      65           6 :             idx += static_cast<int>(
      66           6 :                 std::distance(x.begin(), std::min_element(x.begin(), x.end())));
      67             :         }
      68           6 :         idx /= N_ITERS;
      69           6 :         printf("min at idx %d (using std::min_element)\n", idx);
      70           6 :         auto end = std::chrono::steady_clock::now();
      71           6 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
      72             :     }
      73             :     {
      74           6 :         auto start = std::chrono::steady_clock::now();
      75           6 :         int idx = 0;
      76          12 :         for (int i = 0; i < N_ITERS; ++i)
      77             :         {
      78           6 :             idx += static_cast<int>(
      79           6 :                 gdal::min_element(x.data(), x.size(), eDT, true, noData));
      80             :         }
      81           6 :         idx /= N_ITERS;
      82           6 :         printf("min at idx %d (nodata case, optimized)\n", idx);
      83           6 :         auto end = std::chrono::steady_clock::now();
      84           6 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
      85             :     }
      86             :     {
      87           6 :         auto start = std::chrono::steady_clock::now();
      88           6 :         int idx = 0;
      89          12 :         for (int i = 0; i < N_ITERS; ++i)
      90             :         {
      91           6 :             idx += static_cast<int>(std::distance(
      92             :                 x.begin(), std::min_element(x.begin(), x.end(),
      93   120000000 :                                             [noData](T a, T b) {
      94   120000000 :                                                 return b == noData   ? true
      95    59999800 :                                                        : a == noData ? false
      96    60000000 :                                                                      : a < b;
      97             :                                             })));
      98             :         }
      99           6 :         idx /= N_ITERS;
     100           6 :         printf("min at idx %d (nodata case, using std::min_element with "
     101             :                "nodata aware comparison)\n",
     102             :                idx);
     103           6 :         auto end = std::chrono::steady_clock::now();
     104           6 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     105             :     }
     106           6 : }
     107             : 
     108             : template <class T>
     109             : #if defined(__GNUC__)
     110             : __attribute__((noinline))
     111             : #endif
     112             : static void
     113           2 : benchFloatingPointsWithNaN(GDALDataType eDT, T noData)
     114             : {
     115           2 :     std::vector<T> x;
     116           2 :     x.resize(SIZE);
     117           2 :     randomFill(x.data(), x.size());
     118             :     {
     119           2 :         auto start = std::chrono::steady_clock::now();
     120           2 :         int idx = 0;
     121           4 :         for (int i = 0; i < N_ITERS; ++i)
     122             :         {
     123           2 :             idx += static_cast<int>(
     124           2 :                 gdal::min_element(x.data(), x.size(), eDT, false, 0));
     125             :         }
     126           2 :         idx /= N_ITERS;
     127           2 :         printf("min at idx %d (optimized)\n", idx);
     128           2 :         auto end = std::chrono::steady_clock::now();
     129           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     130             :     }
     131             :     {
     132           2 :         auto start = std::chrono::steady_clock::now();
     133           2 :         int idx = 0;
     134           4 :         for (int i = 0; i < N_ITERS; ++i)
     135             :         {
     136           2 :             idx += static_cast<int>(std::distance(
     137             :                 x.begin(), std::min_element(x.begin(), x.end(),
     138    20000000 :                                             [](T a, T b) {
     139    40000000 :                                                 return std::isnan(b)   ? true
     140    20000000 :                                                        : std::isnan(a) ? false
     141    39902300 :                                                                        : a < b;
     142             :                                             })));
     143             :         }
     144           2 :         idx /= N_ITERS;
     145           2 :         printf("min at idx %d (using std::min_element with NaN aware "
     146             :                "comparison)\n",
     147             :                idx);
     148           2 :         auto end = std::chrono::steady_clock::now();
     149           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     150             :     }
     151             :     {
     152           2 :         auto start = std::chrono::steady_clock::now();
     153           2 :         int idx = 0;
     154           4 :         for (int i = 0; i < N_ITERS; ++i)
     155             :         {
     156           2 :             idx += static_cast<int>(
     157           2 :                 gdal::min_element(x.data(), x.size(), eDT, true, noData));
     158             :         }
     159           2 :         idx /= N_ITERS;
     160           2 :         printf("min at idx %d (nodata case, optimized)\n", idx);
     161           2 :         auto end = std::chrono::steady_clock::now();
     162           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     163             :     }
     164             :     {
     165           2 :         auto start = std::chrono::steady_clock::now();
     166           2 :         int idx = 0;
     167           4 :         for (int i = 0; i < N_ITERS; ++i)
     168             :         {
     169           2 :             idx += static_cast<int>(std::distance(
     170             :                 x.begin(), std::min_element(x.begin(), x.end(),
     171    59804600 :                                             [noData](T a, T b)
     172             :                                             {
     173    40000000 :                                                 return std::isnan(b)   ? true
     174    39902300 :                                                        : std::isnan(a) ? false
     175    39804700 :                                                        : b == noData   ? true
     176    19902300 :                                                        : a == noData   ? false
     177    20000000 :                                                                        : a < b;
     178             :                                             })));
     179             :         }
     180           2 :         idx /= N_ITERS;
     181           2 :         printf("min at idx %d (nodata case, using std::min_element with "
     182             :                "nodata aware and NaN aware comparison)\n",
     183             :                idx);
     184           2 :         auto end = std::chrono::steady_clock::now();
     185           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     186             :     }
     187           2 : }
     188             : 
     189             : template <class T>
     190             : #if defined(__GNUC__)
     191             : __attribute__((noinline))
     192             : #endif
     193             : static void
     194           2 : benchFloatingPointsWithoutNaN(GDALDataType eDT, T noData)
     195             : {
     196           2 :     std::vector<T> x;
     197           2 :     x.resize(SIZE);
     198           2 :     randomFill(x.data(), x.size(), false);
     199             :     {
     200           2 :         auto start = std::chrono::steady_clock::now();
     201           2 :         int idx = 0;
     202           4 :         for (int i = 0; i < N_ITERS; ++i)
     203             :         {
     204           2 :             idx += static_cast<int>(
     205           2 :                 gdal::min_element(x.data(), x.size(), eDT, false, 0));
     206             :         }
     207           2 :         idx /= N_ITERS;
     208           2 :         printf("min at idx %d (optimized)\n", idx);
     209           2 :         auto end = std::chrono::steady_clock::now();
     210           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     211             :     }
     212             :     {
     213           2 :         auto start = std::chrono::steady_clock::now();
     214           2 :         int idx = 0;
     215           4 :         for (int i = 0; i < N_ITERS; ++i)
     216             :         {
     217           2 :             idx += static_cast<int>(
     218           2 :                 std::distance(x.begin(), std::min_element(x.begin(), x.end())));
     219             :         }
     220           2 :         idx /= N_ITERS;
     221           2 :         printf("min at idx %d (using std::min_element)\n", idx);
     222           2 :         auto end = std::chrono::steady_clock::now();
     223           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     224             :     }
     225             :     {
     226           2 :         auto start = std::chrono::steady_clock::now();
     227           2 :         int idx = 0;
     228           4 :         for (int i = 0; i < N_ITERS; ++i)
     229             :         {
     230           2 :             idx += static_cast<int>(
     231           2 :                 gdal::min_element(x.data(), x.size(), eDT, true, noData));
     232             :         }
     233           2 :         idx /= N_ITERS;
     234           2 :         printf("min at idx %d (nodata case, optimized)\n", idx);
     235           2 :         auto end = std::chrono::steady_clock::now();
     236           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     237             :     }
     238             :     {
     239           2 :         auto start = std::chrono::steady_clock::now();
     240           2 :         int idx = 0;
     241           4 :         for (int i = 0; i < N_ITERS; ++i)
     242             :         {
     243           2 :             idx += static_cast<int>(std::distance(
     244             :                 x.begin(), std::min_element(x.begin(), x.end(),
     245    40000000 :                                             [noData](T a, T b) {
     246    40000000 :                                                 return b == noData   ? true
     247    20000000 :                                                        : a == noData ? false
     248    20000000 :                                                                      : a < b;
     249             :                                             })));
     250             :         }
     251           2 :         idx /= N_ITERS;
     252           2 :         printf("min at idx %d (nodata case, using std::min_element with "
     253             :                "nodata aware comparison)\n",
     254             :                idx);
     255           2 :         auto end = std::chrono::steady_clock::now();
     256           2 :         printf("-> elapsed=%d\n", static_cast<int>((end - start).count()));
     257             :     }
     258           2 : }
     259             : 
     260           1 : int main(int /* argc */, char * /* argv */[])
     261             : {
     262             :     {
     263             :         using T = uint8_t;
     264           1 :         constexpr GDALDataType eDT = GDT_Byte;
     265           1 :         printf("uint8:\n");
     266           1 :         benchIntegers<T>(eDT, 0);
     267             :     }
     268           1 :     printf("--------------------\n");
     269             :     {
     270             :         using T = int8_t;
     271           1 :         constexpr GDALDataType eDT = GDT_Int8;
     272           1 :         printf("int8:\n");
     273           1 :         benchIntegers<T>(eDT, 0);
     274             :     }
     275           1 :     printf("--------------------\n");
     276             :     {
     277             :         using T = uint16_t;
     278           1 :         constexpr GDALDataType eDT = GDT_UInt16;
     279           1 :         printf("uint16:\n");
     280           1 :         benchIntegers<T>(eDT, 0);
     281             :     }
     282           1 :     printf("--------------------\n");
     283             :     {
     284             :         using T = int16_t;
     285           1 :         constexpr GDALDataType eDT = GDT_Int16;
     286           1 :         printf("int16:\n");
     287           1 :         benchIntegers<T>(eDT, 0);
     288             :     }
     289           1 :     printf("--------------------\n");
     290             :     {
     291             :         using T = uint32_t;
     292           1 :         constexpr GDALDataType eDT = GDT_UInt32;
     293           1 :         printf("uint32:\n");
     294           1 :         benchIntegers<T>(eDT, 0);
     295             :     }
     296           1 :     printf("--------------------\n");
     297             :     {
     298             :         using T = int32_t;
     299           1 :         constexpr GDALDataType eDT = GDT_Int32;
     300           1 :         printf("int32:\n");
     301           1 :         benchIntegers<T>(eDT, 0);
     302             :     }
     303           1 :     printf("--------------------\n");
     304             :     {
     305             :         using T = float;
     306           1 :         constexpr GDALDataType eDT = GDT_Float32;
     307           1 :         printf("float (*with* NaN):\n");
     308           1 :         benchFloatingPointsWithNaN<T>(eDT, 0);
     309             :     }
     310           1 :     printf("--------------------\n");
     311             :     {
     312             :         using T = float;
     313           1 :         constexpr GDALDataType eDT = GDT_Float32;
     314           1 :         printf("float (without NaN):\n");
     315           1 :         benchFloatingPointsWithoutNaN<T>(eDT, 0);
     316             :     }
     317           1 :     printf("--------------------\n");
     318             :     {
     319             :         using T = double;
     320           1 :         constexpr GDALDataType eDT = GDT_Float64;
     321           1 :         printf("double (*with* NaN):\n");
     322           1 :         benchFloatingPointsWithNaN<T>(eDT, 0);
     323             :     }
     324           1 :     printf("--------------------\n");
     325             :     {
     326             :         using T = double;
     327           1 :         constexpr GDALDataType eDT = GDT_Float64;
     328           1 :         printf("double (without NaN):\n");
     329           1 :         benchFloatingPointsWithoutNaN<T>(eDT, 0);
     330             :     }
     331           1 :     return 0;
     332             : }