-1

Since I don't have much knowledge of multi-threaded design and English is not my native language, I don't know how to exactly describe my problem. Let's say I have a mini-program in school, which has the responsibility to analyze a runtime feed. The feed is a continuous list of messages with the following format:

{"type": "A", "data": [...]} // message for doing task type A
{"type": "B", "data": [...]} // message for doing task type B
{"type": "C", "data": [...]} // message for doing task type C
...

For each message, I need to compute the corresponding task and then log the result to the <task-type>.txt file. Currently, my program synchronously does these tasks line by line. However, the problem is:

  • there are about 100 unique tasks (no data sharing) for 100 types, I believe it is a waste if not apply parallelism.
  • for each type, the corresponding task requires the previous state. For example, given task type A which computes the X from data and X(n-1) from the last message if any, the flow is
message 1: {"type": "A", "data": [...]} --> compute X from data --> log X1 to file
message 2: {"type": "A", "data": [...]} --> compute X from data and X1 --> log X2 to file
message 3: {"type": "A", "data": [...]} --> compute X from data and X2 --> log X3 to file

How can I efficiently apply multi-threaded design to my program? What are the multi-threaded keywords that I can search for this problem (thread pool, work-stealing queue, etc.)?

Edited 06.18.2022: My program should achieve the following requirements:

  1. read the feed sequentially, parse each message, and assign the correct task for the type parsed from the message.
  2. parallelizing the tasks with the awareness that if there is a running task with the same type, this new task needs to wait until the previous task is done.

I am stuck on the solution for step 2. I don't think creating a thread for each type is a good idea because I will make too much thread. So this leads me to a thread pool. But which kind of thread pool can meet the requirement mentioned in step 2?

Is there a generalized term for this problem that I can search for?

4
  • Is this is parsing exercise, i.e. your looking for parallel parsing of the feed?
    – Erik Eidt
    Jun 17 at 19:06
  • Why mix all the types into one feed: wouldn't it be better to keep separate feeds for each type?
    – Erik Eidt
    Jun 17 at 19:08
  • @ErikEidt I cannot change the feed, I have edited my questions, I hope that it will be more clearly to you
    – Long Le
    Jun 18 at 11:12
  • 1
    For only 100 types, just create 100 threads, one for each task type, put them in an array so you can forward to them quickly. This could be a problem if there were 100,000 types but for 100 that should be ok.
    – Erik Eidt
    Jun 18 at 13:28

2 Answers 2

2

For only 100 types, just create 100 threads, one for each type, and let the operating system scheduler handle the scheduling.  Types that are busy will get CPU time and others will wait harmlessly.

I can't see doing something more complicated unless there are additional factors, like thousands upon thousands of types, or, one type is too hot, which would require looking at the problem differently and in more detail.

Store references to the 100 threads in an array so you can forward rather directly to the proper thread.

I would also maybe parse as little of the messages in the dispatcher as possible: just enough to know what type it is (so where to send it) and where the message ends i.e. the next message starts, depending on what you can rely on on the message format.

0

The first step could have one or more workers pulling messages, parsing them and putting them on a separate queue per message type.

The second step could be done by having one worker per queue that process the tasks.

There are a bunch of different ways this could be implemented.

A lower level implementation might use concurrent queues, and separate threads for each worker. The exact implementation will depend on your language and platform, ideally there should be good libraries for such structures already available.

A higher level model could use the actor model, where messages are passed to independent actors that does the computation. There are some programming languages built around this model, and there might be libraries available for your specific platform.

There is also the concept of pipelining, where some systems can allow setting concurrent pipelines steps. But again, it will depend on your specific platform and what libraries are available. A .net example would be DataFlow.

I would however recommend to start by testing your assumptions that parallelism would be required for such a task. Processing 100 items per second could easily be done on a single thread if amount of work per item is fairly small. And multi threaded system introduces a bunch of potential concurrency problem you need to be aware of. So I would start with a single threaded system, and expand it to a multi threaded system in steps. That should give you a better chance of finding concurrency issues when they are introduced.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.