Opened 15 years ago
Closed 15 years ago
#3003 closed defect (fixed)
[PATCH] Improve performance of LUTs in VRTComplexSource
Reported by: | bclaywell | Owned by: | Even Rouault |
---|---|---|---|
Priority: | normal | Milestone: | 1.7.0 |
Component: | GDAL_Raster | Version: | svn-trunk |
Severity: | normal | Keywords: | |
Cc: |
Description
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.
Attachments (1)
Change History (3)
by , 15 years ago
Attachment: | gdal-trunk-lookupvalue.patch added |
---|
comment:1 by , 15 years ago
Owner: | changed from | to
---|---|
Status: | new → assigned |
comment:2 by , 15 years ago
Milestone: | → 1.7.0 |
---|---|
Resolution: | → fixed |
Status: | assigned → closed |
Thanks. This patch was just perfect. Applied verbatim in trunk (r17070).
I had a doubt whether std::lower_bound was not too advanced feature of STL, but it compiles fine with g++ 2.96, so I assume it is OK for any existing C++ compiler ;-)
I also realized we had no regression test for LUT in VRT. So here it is : r17071. I've verified that it returns the same value before and after the patch.