id,summary,reporter,owner,description,type,status,priority,milestone,component,version,severity,resolution,keywords,cc 3003,[PATCH] Improve performance of LUTs in VRTComplexSource,bclaywell,Even Rouault,"We noticed that using large LUTs with `VRTComplexSource` resulted in a significant performance hit. Examining the source revealed that `VRTComplexSource::LookupValue()` implements a sequential search through the LUT array. Attached is a patch against svn trunk reimplementing `VRTComplexSource::LookupValue()` using a binary search instead, decreasing the worst-case complexity from `O(n)` to `O(log2(n))`. The proposed implementation is intended to reproduce the behavior of the current implementation, including upper- and lower-bound enforcement and discontinuity handling, and I ran a small test case on both implementations to verify this. Using a LUT of: {{{ 0 => 10 1 => 11 2 => 12 2 => 13 4 => 14 }}} the current and proposed implementations produce the following identical results: {{{ -1 => 10 0 => 10 1 => 11 2 => 12 2.001 => 13.0005 3 => 13.5 3.999 => 13.9995 4 => 14 5 => 14 }}} Additionally, the current implementation requires that the `padfLUTInputs` array is monotonically non-decreasing in order to function correctly: {{{ int i; for ( i = 0; i < nLUTItemCount; i++ ) { if (dfInput > padfLUTInputs[i]) continue; // ... }}} (The proposed implementation has the same requirement.) However, I wasn't able to find any enforcement of that requirement during the assignment of the `padfLUTInputs` and `padfLUTOutputs` arrays. These arrays are loaded with values in the same order as they are read from the VRT file. In order to prevent `VRTComplexSource::LookupValue()` from silently returning incorrect values in the case that the LUT input values in the VRT file are not monotonically non-decreasing, the patch also includes a test block in `VRTComplexSource::XMLInit()` that checks that each value loaded into the `padfLUTInputs` array is equal to or larger than the value that precedes it, cleaning up and returning `CE_Failure` if the condition is violated. ",defect,closed,normal,1.7.0,GDAL_Raster,svn-trunk,normal,fixed,,