After a bit of tweaking I managed to run your program and obtain the results for
size=8. For debugging purposes add these two lines in
When the program finishes - press enter - this will cause the
shutdown method to be invoked and your program will exit.
I'm running on a 8-core i7 2.2Ghz machine - so your results may vary.
Regarding performance, this is pretty much an inefficient solution and here is why: At each step in the backtracking process - that is for each tried partial solution - you are creating and actor and doing a simple loop which creates more actors for the next proposed solutions.
Now, creating an actor in Akka is pretty fast but I dare say that in your case the overhead of creating an actor is bigger (probably by an order of magnitude, even) than the actual work it is doing - I haven't tested this, but it's likely.
The number of analysed partial solutions here is exponential in the size of the board. That is you are creating an exponential number of actors - this is a lot of overhead and you certainly lose any advantage gained by computing the solutions in parallel.
How can we make this better ? Well, for one, we can create a few less actors.
Lets create a fixed pool of
QueenWorker actors (the same number as the number of cores you have in your computer), and place them behind a SmallesMailboxRouter.
When your workers check the current solution in the processed
Work message instead of creating new actors they will send the new proposed solutions to the router, and the router will dispatch these new
Work messages to its routees, in a uniform fashion.
A worker actor will now process a lot more partial solutions and not just one, as it did until now. That's a much better actual_work/akka_housekeeping ratio than before.
Can we do even better then this ? I think we can, if you model your problem a bit differently. In the queens problem, and in general, in backtracking you are exploring a tree of partial solutions. At each step in your algorithm when you generate more partial solutions from existing ones you are branching your tree. The problem with your approach is that when you are branching in the algorithm you are also branching in the concurrency flow - I'm referring here to the fact that you are sending a new Work message to be processed by another actor. This is fine, but if you add the numbers you'll see that this is a lot of overhead which won't gain you any time advantage.
That is because the granularity of your
Work tasks is very small. You are doing very little work between sending messages - and this affects your performance. You can make your workers explore a much larger chunk of partial solutions before generating new
For example, if you have an 8-core CPU, and the problem has
size=8 then you are better of creating 8 workers and giving to worker K the task to compute the solutions which have the queen sitting on column K in the first line. Now each worker executes only one
Work task which represents roughly 1/8 of the total work - this will give much better results.
Regarding a solution with futures - you can certainly do that but I think the program time will be roughly the same as the actor solution with the fixed pool of actors. But I encourage you to try since I might be wrong.
- Solve n-queens puzzle with akka
- How to get started with Akka Streams?
- How to use an Akka Streams SourceQueue with PlayFramework
- How to use stackable trait pattern with Akka actors?
- Scheduling a task at a fixed time of the day with Akka
- Testing with probabilistic failure of components in Akka (Scala)
- Having problems with Akka 2.1.2 Scheduler ('system' not recognized)
- How to deal with long initialization of an Akka child actor?
- Testing Akka actors that mixin Stash with TestActorRef
- Mapped Diagnostic Context logging with play framewok and akka in java
- Get http headers with akka routing dsl
- build workflow engine with Akka
- Best practices with Akka in Scala and third-party Java libraries
- Implementing long polling in scala and play 2.0 with akka
- Idiomatic way to create a basic HTTP Post request with Akka HTTP
- How to select akka actor with actorSelection?
- Interact with Akka actor outside actors
- How to download a HTTP resource to a file with Akka Streams and HTTP?
- Akka Dead Letters with Ask Pattern
- Akka (2.3.0) fails to load Slf4jEventHandler class with java.lang.ClassNotFoundException
- REST API with Akka in Java
- How do you deal with futures in Akka Flow?
- Scala: Redis client implementation with Akka futures
- Dependency injection with Akka
- Mixing Parallel Collections with Akka
- Is Akka suitable for systems with transient network coverage?
- Akka actors unit testing with Scala
- What is the best way to work with akka from nodejs
- Why does Akka fail with "IllegalStateException: cannot create children while terminating or terminated" when testing with ScalaTest?
- Scala Case Classes vs. Protocol Buffers with Akka over the network
More Query from same tag
- delay implementation in scala
- How to correctly use Akka's Event Stream?
- How to extract table information from a cell in dataframe using Scala in Spark
- print CoordinateMatrix after using RowMatrix.columnSimilarities in Apache Spark
- Unity3D: Convert all game objects to same size irrespective of it's scale
- How do we use net.liftweb.http.js.JsCmds.Script object in lift?
- How does circe parse a generic type object to Json?
- NoSQL (e.g. MongoDB) or RDMS (e.g. PostgreSQL) for new Scala project?
- Scala connection pool library?
- Testing a generated curried function with Scala Test
- scala += assignment oddity on string
- Named Pipes in Scala
- Use of abstract type in a concrete class?
- The reason that inheritance is able to restrict mixin composition target
- Strange exception when using groupBy in slick
- intellij error while importing SBT project
- Union types as bound for type parameters of a trait (scala)
- sbt test-only specific test
- How to filter RDD with sequence list in scala
- fs2.Stream hangs on taking twice
- From a List representation of a Map, to a real Map in Scala
- Adding a count column to my sequence in Scala
- How to read an element from a Scala HList?
- Formatting with an Option[String] in Scala
- Concatenation of lists in Scala
- How does Scala maintains the values of variable when the closure was defined?
- Defining lift for all mappable types
- Can't figure out a Scala Type inheritance, covariance, methods and list issue
- scala - javax.mail.AuthenticationFailedException
- how java scala interoperability works?