Skip to content

Spawn a second spawner for parAlgos #36

@hugosenari

Description

@hugosenari

I was thinking about optimizations for #35 using the following logic:

Serial is T = op * N or O(nop)

proc serial(list, op):
  for i in list:
    op(i)

Parallel is T = op + schedule * N or O(1op + nspawn) limited by available threads

proc parallel(list, op):
  for i in list:
    m.spawn op(i)
  • When our schedule cost is near to 0op: O(1op).
    ie. op takes 1s, spawn takes 1us is (to be precise is O(1op + 0.000.0001*nspawn)).
  • When our schedule cost is half op time: O(1op + 2/nspawn),
    ie. op takes 2us, spawn takes 1us
  • When our schedule cost is equal to op time: O(1op + nspawn),
    ie. op takes 1us, spawn takes 1us

But, algorithms like README example (depth-first search) are more like O(1op + (n log nspawn))

Maybe parAlgos could have similar approach of DFS:

proc recursiveParallel(list, bulksize, op):
  if list.len == 0: return
  let (head, tail) = list.take(bulksize)
  m.spawn serial(head, op)
  for part in tail.take(tail.len / 2)
    m.spawn recursiveParallel(part, bulksize, op)

Or because previous algorithm will make pool busy of scheduling instead of busy of working, two scheduling threads is enough.

  • O(1op + 1spawn + 2/nspawn)
proc parAlgo(list, bulksize, op):
  for slice in list.split(bulksize):
    m.spawn serial(slice, op)

proc parParAlgo(list, bulksize, op):
  let (l,r) = tail.take(tail.len / 2)
  m.spawn parAlgo(l, bulkSize, op)
  m.spawn parAlgo(r, bulkSize, op) # ¹

¹ second call to parAlgo should be made without m.spawn, but is there for readability.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions