Scroll algorithm -- improving fetch and display of data

Question

I would like to set out somewhat of a theoretical problem.

Suppose that I have an infinite scroll, implemented something like as described here: https://medium.com/frontend-journeys/how-virtual-infinite-scrolling-works-239f7ee5aa58. There's nothing fancy to it, suffice it to say that it is a table of data, say NxN, and the user can scroll down and to the right, like a spreadsheet, and it will only show the data in the current view plus minus a handle.

Now, let's also say that it takes approximately 10ms to "fetch and display" the data in that view, with a function such as:

get_data(start_col, end_col, start_row, end_row);

This loads instantly when clicking somewhere in the scroll bar or doing a 'slight scroll' to render the necessary data. However, let's also assume that for every 'unfinished fetch event', that it takes double the time to render the necessary view data (due to memory, gc, and a few other things). So, if I scroll from left-to-right in a slow deliberate fashion, I might generate 100+ scroll events that would trigger the loading of data -- at first there's zero noticeably delay. The fetch happens in under 10ms, but soon it starts taking 20ms, and then 40ms, and now we have something like a noticeable delay, until it will reach over a second to load the necessary data. Additionally, we cannot use something like a debounce/delay, as any delay will be apparent -- the data needs to load instantly when a user clicks/scrolls to a place in the grid.

What considerations would I need to take into account and what would a sample algorithm look like to accomplish this? Here is an example of the user interaction I'd like to have on the data, assuming a 10000 x 10000 spreadsheet (though Excel can load all the data at once) -- https://gyazo.com/0772f941f43f9d14f884b7afeac9f414.

Answer 1

Theory and practice: In theory there is no difference between theory and practice, but in practice there is.

• Theory: everything is clear, but nothing works;
• Practice: everything works, but nothing is clear;
• Sometimes theory meets practice: nothing works and nothing is clear.

Sometimes the best approach is a prototype, and finding the problem interesting, I spent a little time cooking one up, although as a prototype it admittedly has many warts...

In short, the easiest solution to limit a backlog of data fetches appears to simply be setting up a poor man's mutex within the routine that's performing the fetching. (In the code example below, the simulated fetch function is simulateFetchOfData.) The mutex involves setting up a variable outside the function scope such that if false, the fetch is open for use, and if true the fetch is currently underway.

That is, when the user adjusts the horizontal or vertical slider to initiate a fetch of data, the function that fetches the data first checks to see if global variable mutex is true (ie, a fetch is already underway), and if so, simply exits. If mutex is not true, then it sets mutex to true, and then continues to perform the fetch. And of course, at the end of the fetch function, mutex is set to false, such that the next user input event will then pass through the mutex check up front, and perform another fetch...

A couple of notes about the prototype.

• Within the simulateFetchOfData function, there is sleep(100) configured as a Promise which simulates the delay in retrieving the data. This is sandwiched with some logging to the console. If you remove the mutex check, you will see with the console open that while moving the sliders, many instances of simulateFetchOfData are initiated and put into suspense waiting on the sleep (ie, the simulated fetch of data) to resolve, whereas with the mutex check in place, only one instance is initiated at any one time.
• The sleep time can be adjusted to simulate greater network or database latency, so that you can get a feel for the user experience. Eg, networks I'm on experience a 90ms latency for comms across the continental US.
• One other notable is that when finishing a fetch and after resetting mutex to false, a check is performed to determine if the horizontal and vertical scroll values are in alignment. If not, another fetch is initiated. This ensures that despite a number of scroll events possibly not firing due to the fetch being busy, that at minimum the final scroll values are addressed by triggering one final fetch.
• The simulated cell data is simply a string value of row-dash-column number. Eg, "555-333" indicates row 555 column 333.
• A sparse array named buffer is used to hold the "fetched" data. Examining it in the console will reveal many "empty x XXXX" entries. The simulateFetchOfData function is set up such that if the data already is held in buffer, then no "fetch" is performed.

(To view the prototype, simply copy and paste the entire code into a new text file, rename to ".html", and open in a browser. EDIT: Has been tested on Chrome and Edge.)

<html><head>

<script>

function initialize() {

  window.rowCount = 10000;
  window.colCount = 5000;

  window.buffer = [];

  window.rowHeight = Array( rowCount ).fill( 25 );  // 20px high rows 
  window.colWidth = Array( colCount ).fill( 70 );  // 70px wide columns 

  var cellAreaCells = { row: 0, col: 0, height: 0, width: 0 };

  window.contentGridCss = [ ...document.styleSheets[ 0 ].rules ].find( rule => rule.selectorText === '.content-grid' );

  window.cellArea = document.getElementById( 'cells' );

  // Horizontal slider will indicate the left most column.
  window.hslider = document.getElementById( 'hslider' );
  hslider.min = 0;
  hslider.max = colCount;
  hslider.oninput = ( event ) => {
    updateCells();
  }

  // Vertical slider will indicate the top most row.
  window.vslider = document.getElementById( 'vslider' );
  vslider.max = 0;
  vslider.min = -rowCount;
  vslider.oninput = ( event ) => {
    updateCells();
  }

  function updateCells() {
    // Force a recalc of the cell height and width...
    simulateFetchOfData( cellArea, cellAreaCells, { row: -parseInt( vslider.value ), col: parseInt( hslider.value ) } );
  }

  window.mutex = false;
  window.lastSkippedRange = null;

  window.addEventListener( 'resize', () => {
    //cellAreaCells.height = 0;
    //cellAreaCells.width = 0;
    cellArea.innerHTML = '';
    contentGridCss.style[ "grid-template-rows" ] = "0px";
    contentGridCss.style[ "grid-template-columns" ] = "0px";

    window.initCellAreaSize = { height: document.getElementById( 'cellContainer' ).clientHeight, width: document.getElementById( 'cellContainer' ).clientWidth };
    updateCells();
  } );
  window.dispatchEvent( new Event( 'resize' ) );

}

function sleep( ms ) {
  return new Promise(resolve => setTimeout( resolve, ms ));
}

async function simulateFetchOfData( cellArea, curRange, newRange ) {

  //
  // Global var "mutex" is true if this routine is underway.
  // If so, subsequent calls from the sliders will be ignored
  // until the current process is complete.  Also, if the process
  // is underway, capture the last skipped call so that when the
  // current finishes, we can ensure that the cells align with the
  // settled scroll values.
  //
  if ( window.mutex ) {
    lastSkippedRange = newRange;
    return;
  }
  window.mutex = true;
  //
  // The cellArea width and height in pixels will tell us how much
  // room we have to fill.
  //
  // row and col is target top/left cell in the cellArea...
  //

  newRange.height = 0;
  let rowPixelTotal = 0;
  while ( newRange.row + newRange.height < rowCount && rowPixelTotal < initCellAreaSize.height ) {
    rowPixelTotal += rowHeight[ newRange.row + newRange.height ];
    newRange.height++;
  }

  newRange.width = 0;
  let colPixelTotal = 0;
  while ( newRange.col + newRange.width < colCount && colPixelTotal < initCellAreaSize.width ) {
    colPixelTotal += colWidth[ newRange.col + newRange.width ];
    newRange.width++;
  }

  //
  // Now the range to acquire is newRange. First, check if this data 
  // is already available, and if not, fetch the data.
  //

  function isFilled( buffer, range ) {
    for ( let r = range.row; r < range.row + range.height; r++ ) {
      for ( let c = range.col; c < range.col + range.width; c++ ) {
        if ( buffer[ r ] == null || buffer[ r ][ c ] == null) {
          return false;
        }
      }
    }
    return true;
  }

  if ( !isFilled( buffer, newRange ) ) {
    // fetch data!
    for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {  
      buffer[ r ] = [];
      for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
        buffer[ r ][ c ] = `${r}-${c} data`;
      }
    }
    console.log( 'Before sleep' );
    await sleep(100);
    console.log( 'After sleep' );
  }

  //
  // Now that we have the data, let's load it into the cellArea.
  //

  gridRowSpec = '';
  for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {
    gridRowSpec += rowHeight[ r ] + 'px ';
  }

  gridColumnSpec = '';
  for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
    gridColumnSpec += colWidth[ c ] + 'px ';
  }

  contentGridCss.style[ "grid-template-rows" ] = gridRowSpec;
  contentGridCss.style[ "grid-template-columns" ] = gridColumnSpec;

  cellArea.innerHTML = '';

  for ( let r = newRange.row; r < newRange.row + newRange.height; r++ ) {  
    for ( let c = newRange.col; c < newRange.col + newRange.width; c++ ) {
      let div = document.createElement( 'DIV' );
      div.innerText = buffer[ r ][ c ];
      cellArea.appendChild( div );
    }
  }

  //
  // Let's update the reference to the current range viewed and clear the mutex.
  //
  curRange = newRange;

  window.mutex = false;

  //
  // One final step.  Check to see if the last skipped call to perform an update
  // matches with the current scroll bars.  If not, let's align the cells with the
  // scroll values.
  //
  if ( lastSkippedRange ) {
    if ( !( lastSkippedRange.row === newRange.row && lastSkippedRange.col === newRange.col ) ) {
      lastSkippedRange = null;
      hslider.dispatchEvent( new Event( 'input' ) );
    } else {
      lastSkippedRange = null;
    }
  }
}

</script>

<style>

/*

".range-slider" adapted from... https://codepen.io/ATC-test/pen/myPNqW

See https://www.w3schools.com/howto/howto_js_rangeslider.asp for alternatives.

*/

.range-slider-horizontal {
  width: 100%;
  height: 20px;
}

.range-slider-vertical {
  width: 20px;
  height: 100%;
  writing-mode: bt-lr; /* IE */
  -webkit-appearance: slider-vertical;
}

/* grid container... see https://www.w3schools.com/css/css_grid.asp */

.grid-container {

  display: grid;
  width: 95%;
  height: 95%;

  padding: 0px;
  grid-gap: 2px;
  grid-template-areas:
    topLeft column  topRight
    row     cells   vslider
    botLeft hslider botRight;
  grid-template-columns: 50px 95% 27px;
  grid-template-rows: 20px 95% 27px;
}

.grid-container > div {
  border: 1px solid black;
}

.grid-topLeft {
  grid-area: topLeft;
}

.grid-column {
  grid-area: column;
}

.grid-topRight {
  grid-area: topRight;
}

.grid-row {
  grid-area: row;
}

.grid-cells {
  grid-area: cells;
}

.grid-vslider {
  grid-area: vslider;
}

.grid-botLeft {
  grid-area: botLeft;
}

.grid-hslider {
  grid-area: hslider;
}

.grid-botRight {
  grid-area: botRight;
}

/* Adapted from... https://medium.com/evodeck/responsive-data-tables-with-css-grid-3c58ecf04723 */

.content-grid {
  display: grid;
  overflow: hidden;
  grid-template-rows: 0px;  /* Set later by simulateFetchOfData */
  grid-template-columns: 0px;  /* Set later by simulateFetchOfData */
  border-top: 1px solid black;
  border-right: 1px solid black;
}

.content-grid > div {
  overflow: hidden;
  white-space: nowrap;
  border-left: 1px solid black;
  border-bottom: 1px solid black;  
}
</style>


</head><body onload='initialize()'>

<div class='grid-container'>
  <div class='topLeft'> TL </div>
  <div class='column' id='columns'> column </div>
  <div class='topRight'> TR </div>
  <div class='row' id = 'rows'> row </div>
  <div class='cells' id='cellContainer'>
    <div class='content-grid' id='cells'>
      Cells...
    </div>
  </div>
  <div class='vslider'> <input id="vslider" type="range" class="range-slider-vertical" step="1" value="0" min="0" max="0"> </div>
  <div class='botLeft'> BL </div>
  <div class='hslider'> <input id="hslider" type="range" class="range-slider-horizontal" step="1" value="0" min="0" max="0"> </div>
  <div class='botRight'> BR </div>
</div>

</body></html>

Again, this is a prototype to prove out a means to limit a backlog of unnecessary data calls. If this were to be refactored for production purposes, many areas will require addressing, including: 1) reducing the use of the global variable space; 2) adding row and column labels; 3) adding buttons to the sliders for scrolling individual rows or columns; 4) possibly buffering related data, if data calculations are required; 5) etc...

Answer 2

I think you should not send a request at any scroll event. only if by this scroll the user reach the end of the scroll.

if(e.target.scrollHeight - e.target.offsetHeight === 0) {
    // the element reach the end of vertical scroll
}
if(e.target.scrollWidth - e.target.offsetWidth === 0) {
   // the element reach the end of horizontal scroll
}

You also can specify a width which will defined as close enough for fetch a new data (e.i. e.target.scrollHeight - e.target.offsetHeight <= 150)