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: 4 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

Autogenerated LLM Summary (model llama3.2:3b, generated one month 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.

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (X11; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/110.0

Browser/OS: Firefox 110 on Linux

View result in a separate tab

Test name	Executions per second
While Loop with cached parent_id	49385.2 Ops/sec
While Loop no caching parent_id	40938.5 Ops/sec
Using ForEach() instead of While Loop	37674.7 Ops/sec
While Loop without cache, using if/else instead of continue	48730.6 Ops/sec
While Loop without cache, using spread with assign	28821.4 Ops/sec
While Loop without cache, using spread only	58936.9 Ops/sec
For Loop version	47289.8 Ops/sec
Using ForEach() instead of While Loop, spread only	53442.9 Ops/sec
Using ForEach() instead of While Loop, spread only, no push()	52848.4 Ops/sec

Related benchmarks:

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

Created: 4 years ago by: Registered User

Jump to the latest 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()

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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