Benchmark: Tree building performance test w/ larger array (single invocation) v4

Tree building performance test w/ larger array (single invocation) v4 (version: 3)

Comparing performance of: While Loop with cached parent_id vs While Loop no caching parent_id vs Using ForEach() instead of While Loop vs While Loop without cache, using if/else instead of continue vs While Loop without cache, using spread with assign vs While Loop without cache, using spread only vs For Loop version vs Using ForEach() instead of While Loop, spread only vs Using ForEach() instead of While Loop, spread only, no push()

Created: 6 years ago by: Registered User

Jump to the latest result

Script Preparation code:


// Builds a tree from a flat array of objects. Edited from
// stackoverflow.com/questions/18017869 d3indepth.com/layouts
// github.com/inikulin/parse5 github.com/moappi/json2html (node)
function makeLayoutTree(data) {
  const tree = []
  const dict = {}

  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    const pid = data[i].parent_id
    if (pid) {
      dict[pid].children[dict[pid].children.length] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}

// Test version not caching parent_id
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}

// Test version not caching parent_id, Object.assign with
// 2 objects
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, data[i], { children: [] })
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}


// Test version not caching parent_id, Object.assign with spread
// operator
function makeLayoutTree_noCache_assignSpread(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, { ...data[i], children: [] })
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}


// Test version not caching parent_id, with direct spread
// operator only, no Object.create(null)
function makeLayoutTree_noCache_spread(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = { ...data[i], children: [] }
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
      continue
    }
    tree[tree.length] = dict[data[i].id]
  }

  return tree
}

// Test version not caching parent_id, using if/else instead
// continue
function makeLayoutTree_noCache_noContinue(data) {
  const tree = []
  const dict = {}
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign({}, data[i])
    dict[data[i].id].children = []
  }

  i = data.length

  while (i--) {
    if (data[i].parent_id) {
      dict[data[i].parent_id].children[
        dict[data[i].parent_id].children.length
      ] = dict[data[i].id]
    } else {
	  tree[tree.length] = dict[data[i].id]
    }
  }

  return tree
}

// Test version with forEach instead of while loops
function makeLayoutTree_forEach(data) {
  const tree = []
  const dict = {}

  data.forEach(o => {
    dict[o.id] = Object.assign({}, o, { children: [] })
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}

// Test version with forEach instead of while loops, no object.assign
function makeLayoutTree_forEach2(data) {
  const tree = []
  const dict = {}

  data.forEach(o => {
    dict[o.id] = { ...o, children: [] }
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}

// Test version with forEach instead of while loops, no object.assign
function makeLayoutTree_forEach3(data) {
  const tree = []
  const dict = {}

  data.forEach(o => {
    dict[o.id] = { ...o, children: [] }
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children[dict[o.parent_id].children.length] = dict[o.id]
      : tree[tree.length] = dict[o.id]
  })

  return tree
}

// With For Loop instead of While Loop
function makeLayoutTree_forLoop(data) {
  const tree = []
  const dict = {}

  for (let i = 0; i < data.length; i++) {
    dict[data[i].id] = Object.assign({}, data[i])
    dict[data[i].id].children = []
  }

  for (let j = 0; j < data.length; j++) {
    if (data[j].parent_id) {
      dict[data[j].parent_id].children[
        dict[data[j].parent_id].children.length
      ] = dict[data[j].id]
      continue
    }
    tree[tree.length] = dict[data[j].id]
  }

  return tree
}


sample1 = [
  {
    id: 31,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 37,
    parent_id: 32,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 38,
    parent_id: 32,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 45,
    parent_id: 42,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 7,
    parent_id: 3,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 86,
    parent_id: 82,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 43,
    parent_id: 41,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 44,
    parent_id: 42,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 81,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 67,
    parent_id: 62,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 47,
    parent_id: 42,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 23,
    parent_id: 21,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 4,
    parent_id: 3,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 82,
    parent_id: 81,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 74,
    parent_id: 72,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 62,
    parent_id: 61,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 83,
    parent_id: 81,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 27,
    parent_id: 22,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 55,
    parent_id: 52,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 1,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 71,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 48,
    parent_id: 42,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 36,
    parent_id: 32,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 76,
    parent_id: 72,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 2,
    parent_id: 1,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 46,
    parent_id: 42,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 35,
    parent_id: 32,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 53,
    parent_id: 51,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 72,
    parent_id: 71,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 65,
    parent_id: 62,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 73,
    parent_id: 71,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 25,
    parent_id: 22,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 63,
    parent_id: 61,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 68,
    parent_id: 62,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 52,
    parent_id: 51,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 84,
    parent_id: 82,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 66,
    parent_id: 62,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 34,
    parent_id: 32,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 3,
    parent_id: 2,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 58,
    parent_id: 52,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 78,
    parent_id: 72,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 88,
    parent_id: 82,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 33,
    parent_id: 31,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 87,
    parent_id: 82,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 57,
    parent_id: 52,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 8,
    parent_id: 3,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 64,
    parent_id: 62,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 85,
    parent_id: 82,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 21,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 61,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 77,
    parent_id: 72,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 56,
    parent_id: 52,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 28,
    parent_id: 22,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 42,
    parent_id: 41,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 51,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 75,
    parent_id: 72,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 54,
    parent_id: 52,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 6,
    parent_id: 3,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 24,
    parent_id: 22,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 32,
    parent_id: 31,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 22,
    parent_id: 21,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 5,
    parent_id: 3,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 41,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 26,
    parent_id: 22,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
]

Tests:

While Loop with cached parent_id
makeLayoutTree(sample1)
While Loop no caching parent_id
makeLayoutTree_noCache(sample1)
Using ForEach() instead of While Loop
makeLayoutTree_forEach(sample1)
While Loop without cache, using if/else instead of continue
makeLayoutTree_noCache_noContinue(sample1)
While Loop without cache, using spread with assign
makeLayoutTree_noCache_assignSpread(sample1)
While Loop without cache, using spread only
makeLayoutTree_noCache_spread(sample1)
For Loop version
makeLayoutTree_forLoop(sample1)
Using ForEach() instead of While Loop, spread only
makeLayoutTree_forEach2(sample1)
Using ForEach() instead of While Loop, spread only, no push()
makeLayoutTree_forEach3(sample1)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
While Loop with cached parent_id
While Loop no caching parent_id
Using ForEach() instead of While Loop
While Loop without cache, using if/else instead of continue
While Loop without cache, using spread with assign
While Loop without cache, using spread only
For Loop version
Using ForEach() instead of While Loop, spread only
Using ForEach() instead of While Loop, spread only, no push()

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

It looks like we have some benchmarking results for different JavaScript loop constructs!

Let's dive into the data and see what insights we can gain.

**Overall Trends**

* The **For Loop version** has an average execution speed of 47289.8 executions per second (out of 58817).
* Using **ForEach() instead of While Loop, spread only** is slightly faster, with an average execution speed of 53442.9 executions per second.
* Using **ForEach() instead of While Loop, spread only, no push()** is also faster, with an average execution speed of 52848.4 executions per second.
* The **While Loop without cache** consistently performs poorly, with an average execution speed of around 40938 seconds (or approximately 6.9 seconds).
* Using **ForEach() instead of While Loop** without spreading results in a similar performance to the **For Loop version**, which is not surprising given that we're still iterating over the same data.

**Observations**

* The use of caching (`parent_id`) seems to have a positive impact on performance, as seen in the "While Loop with cached parent_id" and "Using ForEach() instead of While Loop, spread only" results.
* Using `if/else` statements (as opposed to `continue`) in the while loop does not seem to provide any significant performance benefits or drawbacks.

**Open Questions**

* Why is the **For Loop version** so much slower than the other two? Is this due to some internal optimization that's being lost when using a for loop?
* What are the implications of caching `parent_id` in the while loops? Is this an optimization technique we should consider?

Overall, it appears that **ForEach() with spreading results** is the fastest approach, followed closely by the **For Loop version**, which might be due to some internal optimizations that are being lost when using a for loop.

Related benchmarks: