Lisp HUG Maillist Archive

Work stealing task queues


I'm trying to speed up traversals of directory hierarchies, while
maintining a cap on the number of open DIR descriptors (basically UNIX
`find'.)  This leads to a formulation where a task unit involves
processing a particular node, and new tasks are generated for
child-nodes: I can push these tasks to multiple task-queues. Prime facie
this seems to be a reasonable way to parallelize this, but for the locks
that need to be grabbed in every task.

The contention issues appear similar to what "work stealing" reportedly
solves.  I'm wondering if there is an implementation of task queues that
someone could share (I believe some of you have worked on it) that I
could try out, or point out the required reading to understand the
situation better.  Appreciate any leads ---Madhu

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html


Re: Work stealing task queues

I've played with these ideas, but don't have concrete measurements on LW.

I'd say: one process per core.  One mailbox, shared by all of these worker processes, containing worklets (lambda functions, or structs).  (Or one coordinator process to mete out the worklets to the per-core workers on individual mailboxes).

Or, an array of worker processes, created once at the beginning of the run.

My experience (embedded systems) says don't spawn processes on the fly - pre allocate them (unless you've got a tuned erlang like vm that doesn't use native processes).

I don't see why you'd need locks, beyond the ones already built into LW mailboxes.

(I'm distracted until after the weekend - ping me then if you'd like more discussion).

Pt

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html


Updated at: 2020-12-10 08:35 UTC