From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA03650 for caml-redistribution@pauillac.inria.fr; Fri, 10 Mar 2000 09:00:52 +0100 (MET) Resent-Message-Id: <200003100800.JAA03650@pauillac.inria.fr> Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA02256 for ; Wed, 8 Mar 2000 21:13:58 +0100 (MET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id VAA25197; Wed, 8 Mar 2000 21:12:37 +0100 (MET) Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA06849; Wed, 8 Mar 2000 21:12:35 +0100 (MET) Message-ID: <20000308211235.24853@pauillac.inria.fr> Date: Wed, 8 Mar 2000 21:12:35 +0100 From: Xavier Leroy To: Julian Assange Cc: William Chesters , caml-list@inria.fr Subject: Re: Interpreter vs hardware threads References: <14518.34203.741447.637489@gargle.gargle.HOWL> <38BC93FC.65E3ED43@in.ot.com.au> <38bd773a@tequila.cs.yale.edu> <200003021818.SAA13646@toy.william.bogus> <20000306183546.18171@pauillac.inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.89.1 In-Reply-To: ; from Julian Assange on Wed, Mar 08, 2000 at 12:19:28AM +1100 Resent-From: weis@pauillac.inria.fr Resent-Date: Fri, 10 Mar 2000 09:00:52 +0100 Resent-To: caml-redistribution@pauillac.inria.fr > What is the source of the linearity of thread context switches in > ocaml? Well, the list of all threads is scanned at each context switch to find runnable threads, determine whether we need to select(), etc. > Are there ways to eliminate it? If so I'd be happy to have a > look at doing so. It's been on my "to do" list for a while, so feel free to give it a try... The standard trick is to split the collection of threads into several queues: a queue of runnable threads and a queue of threads waiting for I/O or timer operations, for instance. Kepp the latter sorted by timer expiration date to find easily the timers that have expired. Also, suspended threads (threads waiting on internal events such as mutexes and conditions) are not in those two queues, but added back to the runnable queue when woken up. This should get the complexity of context switches down to O(N_io), where N_io is the number of threads waiting on I/O. You could do better by using heavyweight threads or signal-based async I/O instead of select(), but it becomes less portable. - Xavier Leroy