Benchmark: Tree building performance test

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 = Object.create(null)

  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), 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 caching len, not caching parent_id
function makeLayoutTree_noCache(data) {
  const tree = []
  const dict = Object.create(null)
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), 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 caching len, not caching parent_id or using
// continue
function makeLayoutTree_noCache_noContinue(data) {
  const tree = []
  const dict = Object.create(null)
  
  let i = data.length

  while (i--) {
    dict[data[i].id] = Object.assign(Object.create(null), 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 = Object.create(null)

  data.forEach(o => {
    dict[o.id] = Object.assign(Object.create(null), o, { children: [] })
  })

  data.forEach(o => {
    o.parent_id
      ? dict[o.parent_id].children.push(dict[o.id])
      : tree.push(dict[o.id])
  })

  return tree
}


sample1 = [
  { id: 1, parent_id: 0 },
  { id: 2, parent_id: 1 },
  { id: 3, parent_id: 1 },
  { id: 4, parent_id: 2 },
  { id: 5, parent_id: 0 },
  { id: 6, parent_id: 0 },
  { id: 7, parent_id: 4 },
]

sample2 = [
  {
    id: 1,
    Phone: '(403) 125-2552',
    City: 'Coevorden',
    Name: 'Grady',
  },
  {
    id: 2,
    parent_id: 1,
    Phone: '(979) 486-1932',
    City: 'Chełm',
    Name: 'Scarlet',
  },
  {
    id: 3,
    parent_id: 2,
    Phone: '(225) 125-2552',
    City: 'Nola',
    Name: 'Jill',
  },
  {
    id: 4,
    parent_id: 3,
    Phone: '(221) 486-1932',
    City: 'BR',
    Name: 'John Boy',
  },
  {
    id: 5,
    parent_id: 3,
    Phone: '(337) 186-1932',
    City: 'Lafayette',
    Name: 'Stevie',
  },
  {
    id: 6,
    parent_id: 3,
    Phone: '(337) 386-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 7,
    parent_id: 3,
    Phone: '(337) 432-1932',
    City: 'NISH',
    Name: 'Lena',
  },
  {
    id: 8,
    parent_id: 3,
    Phone: '(337) 486-1932',
    City: 'NISH',
    Name: 'Lena',
  },
]


sample3 = [
  {
    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) makeLayoutTree(sample2) makeLayoutTree(sample3)
While Loop no caching parent_id
makeLayoutTree_noCache(sample1) makeLayoutTree_noCache(sample2) makeLayoutTree_noCache(sample3)
Using ForEach() instead of While Loop
makeLayoutTree_forEach(sample1) makeLayoutTree_forEach(sample2) makeLayoutTree_forEach(sample3)
While Loop without cache/continue
makeLayoutTree_noCache_noContinue(sample1) makeLayoutTree_noCache_noContinue(sample2) makeLayoutTree_noCache_noContinue(sample3)

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/continue

Fastest: N/A

Slowest: N/A

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

LLMs can make mistakes. Check important info.

I'll do my best to provide an answer based on the provided input data.

From the test cases, I notice that we have four tests:

1. **While Loop with cached parent_id**: This test compares the performance of using a while loop with caching against the original implementation without caching.
2. **While Loop no caching parent_id**: This test compares the performance of using a while loop without caching against the original implementation without caching.
3. **Using ForEach() instead of While Loop**: This test compares the performance of using a foreach loop instead of a while loop against the original implementation.
4. **While Loop without cache/continue**: This test compares the performance of using a while loop without caching or continue statements against the original implementation.

From the latest benchmark result, I see that:

* The "While Loop no caching parent_id" test has the highest execution rate per second (22883.88), suggesting that this implementation is the fastest.
* The "Using ForEach() instead of While Loop" test has a lower execution rate per second (21992.29), indicating that using a foreach loop may not be as efficient as a while loop in this case.
* The "While Loop without cache/continue" test also has a relatively high execution rate per second (21593.98), suggesting that avoiding caching and continue statements can still yield good performance.

To provide a more concrete answer, I would need to know the specific implementation details of the `makeLayoutTree` function, as well as the exact input data used for each test case. However, based on the provided benchmark results, it appears that:

* Using a while loop with caching is likely the fastest approach.
* Avoiding caching and using a continue statement may not be necessary or even beneficial in this case.
* Using a foreach loop instead of a while loop can be a viable alternative, but may not offer significant performance gains.

Please provide more context or clarify any questions you have about my answer!

Latest run results:

Run details: (Test run date: 4 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/78.0.3904.97 Safari/537.36

Browser/OS: Chrome 78 on Mac OS X 10.15.1

View result in a separate tab

Test name	Executions per second
While Loop with cached parent_id	21594.0 Ops/sec
While Loop no caching parent_id	22883.9 Ops/sec
Using ForEach() instead of While Loop	21992.3 Ops/sec
While Loop without cache/continue	22697.5 Ops/sec

Related benchmarks:

Tree building performance test (version: 0)

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/continue

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/continue

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