Opened 11 years ago

Closed 11 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)

gdal-trunk-lookupvalue.patch (2.4 KB) - added by bclaywell 11 years ago.

Download all attachments as: .zip

Change History (3)

Changed 11 years ago by bclaywell

comment:1 Changed 11 years ago by Even Rouault

Owner: changed from warmerdam to Even Rouault
Status: newassigned

comment:2 Changed 11 years ago by Even Rouault

Milestone: 1.7.0
Resolution: fixed
Status: assignedclosed

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.

Note: See TracTickets for help on using tickets.