Skip to content

feat: implement LRU cache for string size measurements (#3955)#6176

Merged
ckifer merged 1 commit intorecharts:mainfrom
shreedharbhat98:feat/enhanced-string-size-caching
Aug 5, 2025
Merged

feat: implement LRU cache for string size measurements (#3955)#6176
ckifer merged 1 commit intorecharts:mainfrom
shreedharbhat98:feat/enhanced-string-size-caching

Conversation

@shreedharbhat98
Copy link
Copy Markdown
Contributor

String Size Caching Improvements

Overview

This document outlines the implementation of LRU (Least Recently Used) cache for string size measurements in Recharts, addressing performance issues described in issue #3955.

Problem Statement

The original string size caching mechanism in Recharts had several limitations:

  1. Inefficient Cache Eviction: Used a "clear all" strategy when cache exceeded 2000 items, causing poor cache hit ratios
  2. No Configurability: Users couldn't adjust cache behavior for their specific use cases
  3. Performance Bottlenecks: Excessive getStringSize calls were causing performance issues with large datasets
  4. Memory Management: No intelligent eviction strategy led to suboptimal memory usage

Solution

LRU Cache Implementation

Implemented a standalone LRUCache class with the following features:

  • O(1) Operations: Get and set operations using JavaScript Map's insertion order
  • Configurable Size: Default 2000 items, user configurable
  • Intelligent Eviction: Removes least recently used items when capacity is reached
  • Memory Efficient: Prevents unbounded memory growth
// Example usage
const cache = new LRUCache<string, number>(1000);
cache.set('key', 42);
const value = cache.get('key'); // Returns 42, moves to most recent

Enhanced DOMUtils

Improved the getStringSize function with:

  • Better Cache Keys: Focus on text-relevant CSS properties only
  • Configurable Behavior: Enable/disable caching, adjust cache size
  • Performance Optimization: Reduced cache misses through better key generation
// Configure caching behavior
configureTextMeasurement({
  cacheSize: 5000,     // Increase for large datasets
  enableCache: true    // Enable/disable caching
});

// Get cache statistics
const stats = getStringCacheStats();
console.log(`Cache size: ${stats.size}/${stats.maxSize}`);

API Reference

Configuration Functions

configureTextMeasurement(config)

Configure text measurement behavior.

Parameters:

  • config.cacheSize (number): Maximum cache size (default: 2000)
  • config.enableCache (boolean): Enable/disable caching (default: true)

Example:

configureTextMeasurement({
  cacheSize: 1000,
  enableCache: false
});

getTextMeasurementConfig()

Get current configuration.

Returns: Current TextMeasurementConfig

clearStringCache()

Clear the entire cache. Useful for testing or memory management.

getStringCacheStats()

Get cache statistics for debugging.

Returns:

{
  size: number;    // Current cache size
  maxSize: number; // Maximum cache size
}

Performance Benefits

Before vs After

Metric Before After
Cache Strategy Clear All LRU Eviction
Cache Hit Ratio Poor (frequent clears) High (intelligent eviction)
Memory Usage Unpredictable spikes Bounded and predictable
Configurability None Full control
Large Dataset Performance Degraded Optimized

Use Case Optimizations

Large Datasets

// Increase cache size for better performance
configureTextMeasurement({ cacheSize: 5000 });

Memory-Constrained Environments

// Reduce cache size to save memory
configureTextMeasurement({ cacheSize: 500 });

Debugging

// Disable caching to isolate issues
configureTextMeasurement({ enableCache: false });

Implementation Details

LRU Cache Algorithm

The LRU cache uses JavaScript's Map data structure, which maintains insertion order:

  1. Get Operation: If key exists, delete and re-insert to mark as most recent
  2. Set Operation: If at capacity, remove first (oldest) item before inserting
  3. Memory Bounds: Never exceeds configured maximum size

Cache Key Generation

Optimized cache keys include only text-relevant CSS properties:

const relevantStyles = {
  fontSize: style.fontSize,
  fontFamily: style.fontFamily,
  fontWeight: style.fontWeight,
  fontStyle: style.fontStyle,
  letterSpacing: style.letterSpacing,
  textTransform: style.textTransform,
};

This reduces cache misses by normalizing keys and ignoring irrelevant style properties.

Testing

Test Coverage

  • LRU Cache: 7 comprehensive tests covering eviction, ordering, and edge cases
  • DOMUtils: 7 tests for configuration options and caching behavior
  • Integration: All existing tests continue to pass (1013/1013)

Test Categories

  1. Functionality Tests: Verify correct cache behavior
  2. Performance Tests: Ensure no regression in performance
  3. Configuration Tests: Validate all configuration options
  4. Edge Cases: Handle boundary conditions and error states

Migration Guide

Existing Code

No changes required! All existing code continues to work:

// This continues to work exactly as before
const size = getStringSize('Hello World', { fontSize: '14px' });

Performance Optimization

For applications with specific needs:

// High-performance mode (larger cache)
configureTextMeasurement({ cacheSize: 5000 });

// Memory-conscious mode (smaller cache)
configureTextMeasurement({ cacheSize: 500 });

// Debug mode (no caching)
configureTextMeasurement({ enableCache: false });

Backward Compatibility

Fully backward compatible

  • All existing APIs work unchanged
  • Default behavior remains identical
  • No breaking changes
  • Existing tests pass without modification

@shreedharbhat98
Copy link
Copy Markdown
Contributor Author

Hi @ckifer / @PavelVanecek 👋
Feel free drop your suggestions.
Thanks!

@PavelVanecek
Copy link
Copy Markdown
Collaborator

How much time does this change save when rendering? How much more memory does it use?

Replaces the previous "clear all" cache strategy with a proper LRU (Least Recently Used)
cache to improve performance and reduce cache misses in text measurement operations.
@shreedharbhat98 shreedharbhat98 force-pushed the feat/enhanced-string-size-caching branch from 62009d0 to 1d0f0ba Compare August 4, 2025 13:34
@shreedharbhat98
Copy link
Copy Markdown
Contributor Author

How much time does this change save when rendering? How much more memory does it use?

Did some bechmarking using the below code snippet.

function getRandomInt(max: number): number {
  return Math.floor(Math.random() * Math.floor(max));
}

interface DataPoint {
  name: string;
  uv: number;
}

const generateData = (n: number): DataPoint[] => {
  const ret: DataPoint[] = [];
  for (let i = 0; i < n; i++) {
    ret.push({ name: `Page ${i}`, uv: getRandomInt(100) });
  }
  return ret;
};

export function LineChartBenchmarkSuite() {
  interface BenchmarkResult {
    dataSize: number;
    dataGenTime: number;
    renderTime: number;
    totalTime: number;
    rating: string;
  }

  const [results, setResults] = useState<BenchmarkResult[]>([]);
  const [isRunning, setIsRunning] = useState(false);
  const [currentTest, setCurrentTest] = useState<number | null>(null);

  const runSingleBenchmark = (dataSize: number): Promise<BenchmarkResult> => {
    return new Promise((resolve) => {
      // Measure data generation
      const dataGenStart = performance.now();
      generateData(dataSize); // Generate data for timing purposes
      const dataGenTime = performance.now() - dataGenStart;

      // Measure rendering
      const renderStart = performance.now();
      performance.mark(`benchmark-${dataSize}-start`);

      // Force a re-render by updating state
      setCurrentTest(dataSize);

      // Measure after React has updated
      setTimeout(() => {
        requestAnimationFrame(() => {
          const renderEnd = performance.now();
          performance.mark(`benchmark-${dataSize}-end`);
          performance.measure(
            `benchmark-${dataSize}`,
            `benchmark-${dataSize}-start`,
            `benchmark-${dataSize}-end`
          );

          const measure = performance.getEntriesByName(
            `benchmark-${dataSize}`
          )[0];
          const totalTime = measure
            ? measure.duration
            : renderEnd - renderStart;
          const renderTime = renderEnd - renderStart;

          const getRating = (time: number) => {
            if (time < 16) return "🟢 Excellent";
            if (time < 50) return "🟡 Good";
            if (time < 100) return "🟠 Fair";
            return "🔴 Slow";
          };

          resolve({
            dataSize,
            dataGenTime: Number(dataGenTime.toFixed(2)),
            renderTime: Number(renderTime.toFixed(2)),
            totalTime: Number(totalTime.toFixed(2)),
            rating: getRating(totalTime),
          });
        });
      }, 0);
    });
  };

  const runFullBenchmark = async () => {
    setIsRunning(true);
    setResults([]);

    const testSizes = [100, 500, 1000, 2000, 5000, 10000];
    const benchmarkResults: BenchmarkResult[] = [];

    for (const size of testSizes) {
      const result = await runSingleBenchmark(size);
      benchmarkResults.push(result);
      setResults([...benchmarkResults]);

      // Small delay between tests to ensure clean measurements
      await new Promise((resolve) => setTimeout(resolve, 200));
    }

    setCurrentTest(null);
    setIsRunning(false);
  };

  const testData = currentTest ? generateData(currentTest) : generateData(1000);

  return (
    <div style={{ padding: 20 }}>
      <div style={{ marginBottom: 20 }}>
        <h3>🧪 LineChart Benchmark Suite (With LRU Cache)</h3>

        <button
          onClick={runFullBenchmark}
          disabled={isRunning}
          style={{
            padding: "10px 20px",
            backgroundColor: isRunning ? "#ccc" : "#007acc",
            color: "white",
            border: "none",
            borderRadius: 4,
            cursor: isRunning ? "not-allowed" : "pointer",
            marginBottom: 15,
          }}
        >
          {isRunning ? "Running Benchmark..." : "Run Performance Benchmark"}
        </button>

        {isRunning && currentTest && (
          <div style={{ color: "blue", marginBottom: 15 }}>
            🔄 Testing {currentTest} data points...
          </div>
        )}
      </div>

      {results.length > 0 && (
        <div style={{ marginBottom: 20 }}>
          <h4>📊 Benchmark Results</h4>
          <table
            style={{
              borderCollapse: "collapse",
              width: "100%",
              border: "1px solid #ddd",
              backgroundColor: "white",
            }}
          >
            <thead>
              <tr style={{ backgroundColor: "#f8f9fa" }}>
                <th
                  style={{
                    padding: 12,
                    textAlign: "left",
                    border: "1px solid #ddd",
                  }}
                >
                  Data Size
                </th>
                <th
                  style={{
                    padding: 12,
                    textAlign: "left",
                    border: "1px solid #ddd",
                  }}
                >
                  Data Gen
                </th>
                <th
                  style={{
                    padding: 12,
                    textAlign: "left",
                    border: "1px solid #ddd",
                  }}
                >
                  Render Time
                </th>
                <th
                  style={{
                    padding: 12,
                    textAlign: "left",
                    border: "1px solid #ddd",
                  }}
                >
                  Total Time
                </th>
                <th
                  style={{
                    padding: 12,
                    textAlign: "left",
                    border: "1px solid #ddd",
                  }}
                >
                  Rating
                </th>
              </tr>
            </thead>
            <tbody>
              {results.map((result, index) => (
                <tr key={index}>
                  <td style={{ padding: 12, border: "1px solid #ddd" }}>
                    {result.dataSize} items
                  </td>
                  <td style={{ padding: 12, border: "1px solid #ddd" }}>
                    {result.dataGenTime}ms
                  </td>
                  <td style={{ padding: 12, border: "1px solid #ddd" }}>
                    {result.renderTime}ms
                  </td>
                  <td style={{ padding: 12, border: "1px solid #ddd" }}>
                    {result.totalTime}ms
                  </td>
                  <td style={{ padding: 12, border: "1px solid #ddd" }}>
                    {result.rating}
                  </td>
                </tr>
              ))}
            </tbody>
          </table>
        </div>
      )}

      <div style={{ border: "1px solid #ddd", padding: 10 }}>
        <p>Current test data: {testData.length} items</p>
        <LineChart
          width={1400}
          height={500}
          data={testData}
          margin={{ top: 5, right: 30, left: 20, bottom: 5 }}
        >
          <XAxis dataKey="name" />
          <YAxis />
          <CartesianGrid strokeDasharray="3 3" />
          <Tooltip />
          <Legend />
          <Line
            dot={false}
            isAnimationActive={false}
            type="monotone"
            dataKey="uv"
            stroke="#82ca9d"
          />
        </LineChart>
      </div>
    </div>
  );
}

Result:

Chrome:

Before After
with cache   chrome Screenshot 2025-08-04 at 6 52 34 PM

Safari:

Before After
with cache   safari Screenshot 2025-08-04 at 6 54 05 PM

Firefox:

Before After
with cache   FF Screenshot 2025-08-04 at 6 54 43 PM

Examples

Without Cache: Codesandbox
With Cache: Codesandbox

Although I did not feel much difference. One thing for sure, Safari's speed is on another level 🙌

@codecov
Copy link
Copy Markdown

codecov bot commented Aug 4, 2025

Codecov Report

❌ Patch coverage is 97.50000% with 2 lines in your changes missing coverage. Please review.
✅ Project coverage is 96.74%. Comparing base (a1e07aa) to head (1d0f0ba).
⚠️ Report is 4 commits behind head on main.

Files with missing lines Patch % Lines
src/util/DOMUtils.ts 96.07% 2 Missing ⚠️
Additional details and impacted files
@@            Coverage Diff             @@
##             main    #6176      +/-   ##
==========================================
+ Coverage   96.53%   96.74%   +0.20%     
==========================================
  Files         217      222       +5     
  Lines       19835    19985     +150     
  Branches     4087     4137      +50     
==========================================
+ Hits        19148    19334     +186     
+ Misses        681      645      -36     
  Partials        6        6              

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@ckifer
Copy link
Copy Markdown
Member

ckifer commented Aug 4, 2025

It would have the exact same results unless you re-use words right? "Page" and then whatever numbers happen to collide on the Y axis but that's not a great hit ratio.

Tbh there probably would never be the best hit ratio because of the nature of a chart

@shreedharbhat98
Copy link
Copy Markdown
Contributor Author

It would have the exact same results unless you re-use words right? "Page" and then whatever numbers happen to collide on the Y axis but that's not a great hit ratio.

Tbh there probably would never be the best hit ratio because of the nature of a chart

May be I agree.
How are we going about it? What could be the good solution here?

@ckifer
Copy link
Copy Markdown
Member

ckifer commented Aug 4, 2025

There isn't much that can make the cache better because it needs exact matches. "Test" is not going to measure the same as "Recharts", etc. caching individual letters isn't an option because initial performance will bad and we'll have to stitch things together.

The only alternative way to measure text is to use canvas and that doesn't result in the same measurement result

@shreedharbhat98
Copy link
Copy Markdown
Contributor Author

shreedharbhat98 commented Aug 5, 2025

There isn't much that can make the cache better because it needs exact matches. "Test" is not going to measure the same as "Recharts", etc. caching individual letters isn't an option because initial performance will bad and we'll have to stitch things together.

The only alternative way to measure text is to use canvas and that doesn't result in the same measurement result

In this I think the only issue that we can solve is

  • Avoid purging the whole cache when over the 2000 keys and evict key on a FIFO basis.
    WDYT?

FYI tried canvas based implementation as well. It did not turn well.

@ckifer
Copy link
Copy Markdown
Member

ckifer commented Aug 5, 2025

Pretty much yep. I think we can merge this, it's not that much more code. Just know that it doesn't fix the problem

@ckifer ckifer merged commit e56913d into recharts:main Aug 5, 2025
20 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants