473,322 Members | 1,501 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Producer/consumer Queue "trick"

WEBoggle needs a new game board every three minutes. Boards take an
unpredictable (much less than 3min, but non-trivial) amount of time to
generate. The system is driven by web requests, and I don't want the
request that happens to trigger the need for the new board to have to
pay the time cost of generating it.

I set up a producer thread that does nothing but generate boards and put
them into a length-two Queue (blocking). At the rate that boards are
pulled from the Queue, it's almost always full, but my poor consumer
thread was still being blocked for "a long time" each time it fetched a
board.

At this point I realized that q.get() on a full Queue immediately wakes
up the producer, which has been blocked waiting to add a board to the
Queue. It sets about generating the next board, and the consumer
doesn't get to run again until the producer blocks again or is preempted.

The solution was simple: have the producer time.sleep(0.001) when
q.put(board) returns.

Cheers,

Evan @ 4-am

Jul 18 '05 #1
7 2342
I don't get it.

If the consumer and the producer are separate threads,
why does the consumer thread block when the producer
thread is generating a new board? Or why does it
take forever for the producer thread to be pre-empted?

Also, I don't understand why the solution works.
How does sleeping for .001 seconds right after putting
a new board on the queue solve the problem?

Evan Simpson wrote:
WEBoggle needs a new game board every three minutes. Boards take an
unpredictable (much less than 3min, but non-trivial) amount of time to
generate. The system is driven by web requests, and I don't want the
request that happens to trigger the need for the new board to have to
pay the time cost of generating it.

I set up a producer thread that does nothing but generate boards and put
them into a length-two Queue (blocking). At the rate that boards are
pulled from the Queue, it's almost always full, but my poor consumer
thread was still being blocked for "a long time" each time it fetched a
board.

At this point I realized that q.get() on a full Queue immediately wakes
up the producer, which has been blocked waiting to add a board to the
Queue. It sets about generating the next board, and the consumer
doesn't get to run again until the producer blocks again or is preempted.

The solution was simple: have the producer time.sleep(0.001) when
q.put(board) returns.

Jul 18 '05 #2
Evan Simpson <ev**@tokenexchange.com> writes:
wakes up the producer, which has been blocked waiting to add a board
to the Queue. It sets about generating the next board, and the
consumer doesn't get to run again until the producer blocks again or
is preempted.


That's weird. Preemption should happen every few dozen milliseconds
unless you've purposely increased the preemption delay.
Jul 18 '05 #3
Paul Rubin wrote:
Evan Simpson <ev**@tokenexchange.com> writes:
wakes up the producer, which has been blocked waiting to add a board
to the Queue. It sets about generating the next board, and the
consumer doesn't get to run again until the producer blocks again or
is preempted.

That's weird. Preemption should happen every few dozen milliseconds
unless you've purposely increased the preemption delay.


To me, it smells like a call into a C extension which isn't releasing the GIL
before starting a time-consuming operation. After getting bitten by this a
couple of times, I now make sure to release the GIL as part of my SWIG wrapper
(since the code I'm wrapping knows nothing of Python, and sure as heck doesn't
need to be holding the GIL!).

Cheers,
Nick.

--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net
Jul 18 '05 #4
On Fri, 14 Jan 2005 16:26:02 -0600, Evan Simpson wrote:
WEBoggle needs a new game board every three minutes. Boards take an
unpredictable (much less than 3min, but non-trivial) amount of time to
generate.


I gotta ask, why?

Looking over your information about "how to play", my only guess is that
you're generating all possible words that may exist in the board, at the
time of board generation.

But it also looks like you score once at the end (as you have to anyhow in
order to cancel out words found by multiple people, according to the rules
of Boggle).

If both of these statements are true, the generation of all possible words
is a waste of time. For each word given by a human, looking it up in the
dict and verifying it is on the board at score time should be a lot
faster, and not need any pre-processing.

If you're generating stats about what percentage of possible words were
found, that can also be done during game play without loss by handing
outh the board, and *then* finding all words. You still have a threading
problem, but now instead of dealing with human response times, you've got
a three minute deadline which ought to be enough.

(The other thing I can think of is that you are trying to verify that the
board contains some minimal number of words, in which case I submit that
boards with only 20-ish words is just part of the game :-) I've never sat
down and really studied the Boggle dice, but I've always expected/hoped
that there is at least one or two dice with all vowels; even so the odds
of no vowels are small and easily algorithmically discarded. )

To be clear, I'm mostly curious what's going on, but it is possible that
the fundamental problem may be algorithmic, and since I don't know what's
going on it's worth checking.

Also, entirely separate plug, you may be interested in my XBLinJS project:
http://www.jerf.org/resources/xblinjs . (I'm expecting to release 0.2
either today or tomorrow, which will have vastly more documentation and
more online examples.) It'd help pull out relevant code so that it is
easily re-usable in any future gaming projects by others.
Jul 18 '05 #5
I should clarify up front that I may have given an overblown sense of
how long the producer thread typically takes to generate a board; It's
usually a few tenths of a second, up to a few seconds for especially
fecund boards.

My concern was that even a few seconds is long enough for fifty requests
to get piled up, and I was experiencing mysterious breakdowns where
Apache was suddenly totally clogged up and taking *minutes* to respond.

Jeremy Bowers wrote:
Looking over your information about "how to play", my only guess is that
you're generating all possible words that may exist in the board, at the
time of board generation.
Yep. I do this in order to minimize the cost of the most common request
that WEBoggle handles, which is checking a submitted word to see whether
it is a valid word on the board, a valid word not on the board, or an
invalid word. With the current code, this averages 1ms.
But it also looks like you score once at the end (as you have to anyhow in
order to cancel out words found by multiple people, according to the rules
of Boggle).
WEBoggle is a little different than regular Boggle, in that your score
is the plain sum of the scores for all of the words that you found, with
no cancellation. I'm planning to add a "vs." feature eventually that
will involve cancellation, but even then I'll retain the immediate
feedback upon guessing a word.

In addition, many players enjoy seeing the list of "Words not found by
anyone".
(The other thing I can think of is that you are trying to verify that the
board contains some minimal number of words, in which case I submit that
boards with only 20-ish words is just part of the game :-) I've never sat
down and really studied the Boggle dice, but I've always expected/hoped
that there is at least one or two dice with all vowels; even so the odds
of no vowels are small and easily algorithmically discarded. )
Believe it or not, before I added code to filter them out, I was
generating enough boards with *zero* valid words on them to get complaints.
Also, entirely separate plug, you may be interested in my XBLinJS project


Very nifty! Well beyond my current needs, but good to know about.

Cheers,

Evan @ 4-am

Jul 18 '05 #6
Jon Perez wrote:
If the consumer and the producer are separate threads,
why does the consumer thread block when the producer
thread is generating a new board? Or why does it
take forever for the producer thread to be pre-empted?

Also, I don't understand why the solution works.
How does sleeping for .001 seconds right after putting
a new board on the queue solve the problem?


I'm guessing at how things work, and may be totally wrong, but here's
what I think happens: In the Queue get() code, the consumer releases
the 'fsema' lock. Directly or indirectly, this wakes up and hands
control to the producer thread, which was blocked trying to acquire
'fsema'. The sleep() hands control back to the scheduler immediately,
which appears to wake up the consumer and let it get on with things.

It doesn't take "forever" for the producer to be preempted, just the
normal preemption interval. I was bothered, though, by the idea of
having it take even a few dozen milliseconds out of the middle of a
request that's at most a millisecond or two away from finishing anyway.

Cheers,

Evan @ 4-am

Jul 18 '05 #7
Nick Coghlan wrote:
Paul Rubin wrote:
That's weird. Preemption should happen every few dozen milliseconds
unless you've purposely increased the preemption delay.

To me, it smells like a call into a C extension which isn't releasing
the GIL before starting a time-consuming operation.


Sorry, I think I misled you both -- "a long time" is actually the few
dozen milliseconds of a normal preemption, which is only long relative
to the single millisecond that the consumer typically takes to handle a
request.

Cheers,

Evan @ 4-am

Jul 18 '05 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Wonjae Lee | last post by:
I read the comment of http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/277753. (Title : Find and replace string in all files in a directory) "perl -p -i -e 's/change this/..to this/g'"...
2
by: Michael Lehn | last post by:
I want to use the "Barton Nackman trick" for my matrix hierarchy. But I ran into a problem with a typedef I need in the base class: template <typename E> class Matrix { public: typedef...
10
by: qazmlp | last post by:
There are some blocks of C/C++ code put under #if 0 #end if Is there anyway to make the code inside these blocks to get executed (may be by using some command line options)?
13
by: royaltiger | last post by:
I am trying to copy the inventory database in Building Access Applications by John L Viescas but when i try to run the database i get an error in the orders form when i click on the allocate...
20
by: Tony | last post by:
I have a situation where I want to send data, but I have no need for a response. It seems to me that XMLHTTPRequest is the best way to send the data, but I don't need any response back from the...
7
by: PW | last post by:
Hi, I have a form with unbound fields on it. The user selects a record from a recordset and I populate the unbound fields. When I try to change the unbound quantity text box, Access 2003 tells...
21
by: comp.lang.tcl | last post by:
set php {<? print_r("Hello World"); ?>} puts $php; # PRINTS OUT <? print_r("Hello World"); ?> puts When I try this within TCL I get the following error:
6
by: =?ISO-8859-1?Q?Une_B=E9vue?= | last post by:
i'd like to intercept the window.onload event in order to distribute it, as needed, to several methods. example : suppose i have several methods doing unlinked initialisations: ...
56
by: Adem | last post by:
C/C++ language proposal: Change the 'case expression' from "integral constant-expression" to "integral expression" The C++ Standard (ISO/IEC 14882, Second edition, 2003-10-15) says under...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.