[erlang-questions] Trying to learn the Erlang Way

Thu Feb 13 20:25:21 CET 2014

On Wed, Feb 12, 2014 at 10:48 PM, Gustav Simonsson <
gustav.simonsson@REDACTED> wrote:

> Apologies if this is completely wrong, but:
>
> Wouldn't one process for each particle, given thousands of particles, pose
> a potential overhead problem given the extra scheduling required between
> processes?
>
>
Without building a prototype and *measuring* I haven't a clue. "thousands"
sounds small to me.
Given 4GB of ram on my machine each process could have 4MB (if there were
1000 processes)
which is *huge* compared to the minimum Erlang process size (300 bytes) and
there will be several
schedulers (on a multicore) so I wouldn't worry.


/Joe


> I would be inclined to try one process for each 3d cube, as you mentioned,
> and also let that process keep track of all particles within its cube
> (maybe in a ETS table). Then, if a particle crosses over to another cube,
> the particle would be migrated from one process to another (via a message
> sent between the two cube processes).
>
> To answer your other points of debate:
>
> 1. This is a very interesting problem which for graphics from a first
> person point of view is well researched, but since this is for some backend
> serving a game/simulation it (I suppose) involves multiple
> players/entities, so we wouldn't want the 3D space to be asymmetrically
> partitioned if we could avoid it (atleast to start with).
>
> If it makes sense given the properties of the 3D space, particles and
> other objects/players you have, one way to reduce the maximum shapes
> overlapping with the sphere of influence to 4 is to partition the space
> into a set of symmetrical cuboids where the Z-axis of each cuboid goes from
> the minimum to the maximum of the space, and the X and Y sizes of the
> cuboids remain strictly larger than the diameter of the sphere (as you
> mentioned for the cube partitioning).
>
> 2. I guess the particles, whether they have their own process or are
> handled inside a cube (or cuboid!) process are in memory anyway, so I'd
> wait with caching anything until its time to optimize a working
> implementation.
>
> 3. The general advice is to save tweaking the BEAM schedulers and which
> scheduler a process runs in for the later stages of optimization. But for
> reference, you can bind a process to a specific scheduler [1] and also bind
> a scheduler to a specific CPU thread (logical processor) [2].
>


>
> Cheers,
> Gustav
>
> [1] Use the {scheduler, N} option (undocumented) to
> erlang:spawn_opt/2,3,4,5. The number of schedulers can be found with
> erlang:system_info(schedulers)
> , and the scheduler for the calling process with
> erlang:system_info(scheduler_id).
>
> [2] Look at the +sbt options at
> http://www.erlang.org/doc/man/erl.html#emu_flags
>
>
>
>
> On Wed, Feb 12, 2014 at 9:48 PM, kraythe . <kraythe@REDACTED> wrote:
>
>> Joe,
>>
>> The problems of gaming are similar for sure but the scale here is much
>> larger. But I can throw another monkey wrench into the mix. The motion of
>> the particles are non-deterministic and can be acted upon by an external
>> force. So each particle needs to have its own life and own process. What I
>> had thought of doing is the following and i would be appreciative of the
>> experience of you and the other erlang gurus in commenting on my proposals:
>>
>> I essentially thought to have each particle be its own process.
>> Furthermore, the world would be divided up into 3d cubes, each of which is
>> at least larger than the maximum radius of the sphere of influence. Each 3d
>> cube would be a process as well and the. The particle process would track
>> which cube it is in and the cubes would track which particles are in them.
>> Then when the motion happens at each frame if the particle leaves a cube,
>> it will send a message to that cube indicating it left and it will also
>> send a message to the new cube that it entered. When determining the
>> particles in the field, the particle would determine whether its sphere
>> spanned multiple cubes and ask each cube which it overlaps to send it a
>> message with the list of particles in the cube. Then it would apply our
>> "in_sphere" test to determine the actual candidates to interact with and
>> then execute those interractions.
>>
>> Points of debate for me are:
>> 1) Should they be cubes dividing the space or another shape. If we use
>> cubes, the maximum number of cubes a sphere could overlap would be 8 if the
>> cubes are arranged in a regular pattern. Alternatively we could use an
>> irregular pattern like a brick layer and then the max number of cubes to
>> check is 5. Are there any other configurations that don't have any overlap
>> of spatial partitioning and could reduce the number of candidate cells
>> further without complicating the math badly.
>> 2) is it worth it to cache, in some manner, the particles in the sphere
>> of influence. I am leaning towards "no" because all will have to be checked
>> to see if they moved out anyway and then the other candidates will have to
>> be checked if they moved in. So there seems little reason to cache anything.
>> 3) Is it worth it to manually move processes around cores as they
>> transition to other areas of geometry (i.e. if the particle is on core 8 of
>> machine 5 but its bounding cube is on core 2 of node 1 there could be
>> inefficiency.) This question is largely a result of my newbieness to OTP
>> and erlang I suppose. If we do move the actor around we will have to
>> reconnect the "client" governing the particle motion to the new actor.
>>
>> Interesting problem huh?
>>
>>
>> *Robert Simmons Jr. MSc. *
>>
>>
>> On Wed, Feb 12, 2014 at 1:42 PM, Joe Armstrong <erlang@REDACTED> wrote:
>>
>>> Interesting problem.
>>>
>>> How to you map your problem onto a process structure?
>>>
>>> Method 1 - let the process manage regions of space
>>>
>>> How about starting with 1000 parallel processes. Each one managing a
>>> point in a 10x10x10 grid in 3-d space.
>>>
>>> In pass one you compute which process "owns" each particle. Thereafter
>>> each process only manages the
>>> particles that it owns. Once it knows the velocity and position of each
>>> particle it can compute if the particle
>>> will leave the zone in the next time tick. In the case when a particle
>>> leaves a zone, you just send a message
>>> to the next zone controller process that you predict it will move to.
>>>
>>> I know that some games companies use this technique for large multi-user
>>> games written in Erlang. They use a 2D map of squares and each square is
>>> controlled by an Erlang processes. This scales nicely on a cluster, since
>>> moving off a map square just moves the computation to a new processes and
>>> possible a
>>> new node.
>>>
>>> Method 2 - let the processes manage a limited set of processes
>>>
>>> I guess if you didn't have too many particles you could have one process
>>> per particle. Each process
>>> could have a "gossip" set (the set of "nearby in space" processes) which
>>> send messages to it's neighbours as things happen. Or you could let one
>>> process handle 10 particles ...
>>>
>>> I guess it al depends on the numbers - I don't think you said how many
>>> particles there were etc.
>>> I always like to know some numbers - are we talking millions or
>>> thousands of particles? How many
>>> interactions/sec take place etc.
>>>
>>> In any case you'll have to model the problem in different ways and
>>> measure.
>>>
>>> Cheers
>>>
>>> /Joe
>>>
>>>
>>>
>>>
>>>
>>> On Wed, Feb 12, 2014 at 6:56 PM, kraythe . <kraythe@REDACTED> wrote:
>>>
>>>> Ahh octtree is good if the objects are static and if your goal is to
>>>> find an object in a large space. It is a reductive search algorithm. In
>>>> this case all of the objects are in motion and I want to know my neigbors,
>>>> not find object X in the space. Therefore a different approach is called
>>>> for.
>>>>
>>>>  Imagine thousands of particles flowing around in a medium and needing
>>>> to determine their interactions based on vicinity, momentum, etc. From
>>>> frame to frame the state of your tree would change and the cost would make
>>>> the simulation impossible to render in realtime. Instead if the world is
>>>> divided up into cubes that are larger than the sphere of influence and each
>>>> cube knows about its neighbors then I can easily get a candidate list as
>>>> long as the particles update the cube entity that they are in. As they move
>>>> into a cube, they inform the cube that they have entered and as they leave
>>>> the cube, they inform it of their exit. If I know the cube I am in, and I
>>>> know my sphere of influence overlaps into another cube, I can immediately
>>>> exclude all candidate not in either cube. If the cube has references to its
>>>> neigbors, the solution is easy.
>>>>
>>>> 1) Determine if I overlap sphere into neighbors (simple math problem of
>>>> the radius of my sphere and the boinds of the cube.
>>>> 2) For all cubes I overlap, get members.
>>>> 3) For all members determine which are inside my sphere.
>>>> 4) Interract with elements in my sphere.
>>>>
>>>> Incidentally my current version of the code, Thanks to Richard's input,
>>>>  is:
>>>>
>>>> %% Subtract the second vector from the first
>>>> subtract({X1, Y1, Z1}, {X2, Y2, Z2}) -> {(X1 - X2), (Y1 - Y2), (Z1 -
>>>> Z2)}.
>>>>
>>>> %% Compute if the vector T is in the sphere with center at vector C and
>>>> with radius R.
>>>> in_sphere(C, R, T) ->
>>>>   {Dx, Dy, Dz} = subtract(C, T),
>>>>   Dx * Dx + Dy * Dy + Dz * Dz =< R * R.
>>>>
>>>> %% Calculate all entities in the sphere defined at center vector C with
>>>> radius R and using Fpos which will extract the location to check from
>>>> %% each entity in the list. The method Fpos must return a three tuple
>>>> vector and take the entity as an argument.
>>>> entities_in_sphere(C ,R, Entities, Fpos) ->
>>>>   [E || E <- Entities, in_sphere(C, R, Fpos(E))].
>>>>
>>>> It also appears to run quite fast according to preliminary timer:tc
>>>> tests but of course there is need for more massive testing of load. I may
>>>> still have to use the type optimization richard pointed out. I am debating
>>>> staying with integer arithmetic also.
>>>>
>>>>
>>>> *Robert Simmons Jr. MSc. *
>>>>
>>>>
>>>> On Wed, Feb 12, 2014 at 8:04 AM, Joe Armstrong <erlang@REDACTED>wrote:
>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Tue, Feb 11, 2014 at 11:17 PM, kraythe . <kraythe@REDACTED> wrote:
>>>>>
>>>>>> Richard,
>>>>>>
>>>>>> I appreciate your response and the effort you put into it. And I
>>>>>> learned a lot from it. In this case I am learning the thinking mode of
>>>>>> Erlang as it is different a bit from what I do to pay the bills. I have yet
>>>>>> to get into list comprehensions in Erlang so that is on my ... well ...
>>>>>> list. :) You have provided valuable insight.
>>>>>>
>>>>>> The main focus of the method is if I have a number of objects with a
>>>>>> vector position in a simulation and I want to exclude considerations of
>>>>>> interactions with objects outside the sphere of influence, I have to
>>>>>> quickly discard the candidates that are not inside the sphere of influence.
>>>>>> I originally thought to write a method that did just the vector math
>>>>>> because I was wondering if that kind of math would have to ultimately be
>>>>>> turned into something native. Even a delay of 1 second would be fatal to
>>>>>> the simulation.
>>>>>>
>>>>>
>>>>> Isn't this what octrees are for? - You'd have to use a "cube of
>>>>> influence" - but as far as I know octrees
>>>>> can be used to rapidly partition objects in a 3-d space
>>>>>
>>>>> Take a look at this http://en.wikipedia.org/wiki/Octree
>>>>>
>>>>> /Joe
>>>>>
>>>>>
>>>>>>
>>>>>> The algorithm, however, shouldnt have to consider all candidates as
>>>>>> the world is broken into spacial segments (cubes) such that the sphere
>>>>>> could intersect with at maximum 8 neighboring cubes so I would only need to
>>>>>> consider simulation objects within those 8 cube spaces when determining
>>>>>> which elements were actually within the sphere of influence. I have been
>>>>>> trying to devise a method of reducing the candidate set even further and am
>>>>>> still working on that. Perhaps edge detection and cube boundary
>>>>>> calculations but I don't want to spend more math doing that then I would
>>>>>> simply excluding objects vector by vector.
>>>>>>
>>>>>> Anyway thanks for the reply, definitely some information that I can
>>>>>> use in there.
>>>>>>
>>>>>> *Robert Simmons Jr. MSc.*
>>>>>>
>>>>>> On Sun, Feb 9, 2014 at 10:59 PM, Richard A. O'Keefe <
>>>>>> ok@REDACTED> wrote:
>>>>>>
>>>>>>>
>>>>>>> On 8/02/2014, at 4:53 AM, kraythe . wrote:
>>>>>>> > Anyway back to the subject at hand. The algorithm is set but now I
>>>>>>> am at another quandary Lets say these vectors represent a position in space
>>>>>>> of particular objects in a simulation. The process of culling the vectors
>>>>>>> based on the sphere is entirely a vector problem but what the user calling
>>>>>>> cull/3 really needs to know is which objects are not culled from the list,
>>>>>>> not just which vectors are not culled. Now in Java I could do a number of
>>>>>>> things if I wanted to keep the cull algorithm as it is. I could return the
>>>>>>> list of integers containing the original indexes of the vectors in the list
>>>>>>> that were culled and use that to filter out which objects need to be
>>>>>>> considered for the simulation step.
>>>>>>>
>>>>>>> The word "cull" really grates.
>>>>>>>
>>>>>>> And all those negations *really* confused me *all over again*.
>>>>>>> I wrote a lengthy and helpful description of how to get the
>>>>>>> points that were accepted and the points that were rejected
>>>>>>> as two lists, because that was the only way I could interpret
>>>>>>> your question to make sense in Erlang.  But on repeated re-reading
>>>>>>> it became clear that you were asking for something else.
>>>>>>>
>>>>>>> There is no such thing in Erlang as object identity.
>>>>>>> The distinction you are drawing between the "points" and the
>>>>>>> "objects" simply doesn't exist.
>>>>>>>
>>>>>>> It so happens that if you use a list comprehension like
>>>>>>>         [P || P <- Points, some_predicate(P)]
>>>>>>> the elements of the result *will* be (references to) the same
>>>>>>> implementation-level webs of chunks of memory that were in the
>>>>>>> original list, not copies.  But nothing other than performance
>>>>>>> depends on this.
>>>>>>>
>>>>>>> A list of integers such as you ask for could be obtained, but it
>>>>>>> would be very little use to you, because Erlang lists are *LINKED
>>>>>>> LISTS*, not *INDEXED ARRAYS*.   Finding the nth element of a list
>>>>>>> takes O(n) time, and that could not be changed without making
>>>>>>> lists much less useful.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> erlang-questions mailing list
>>>>>> erlang-questions@REDACTED
>>>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>>>
>>>>>>
>>>>>
>>>>
>>>> _______________________________________________
>>>> erlang-questions mailing list
>>>> erlang-questions@REDACTED
>>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140213/850b7f14/attachment.htm>