## Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
• Create your own community
##### Activity
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab

I am a bit confused by this error:

Cannot apply "reduce_by_index_stream" to "interaction" (invalid type).
Expected: *acc [n](((f32, f32, f32), (f32, f32, f32)), tââ) -> bââ

-> *acc [n](((f32, f32, f32), (f32, f32, f32)), tââ)
Actual:   (acc: *acc [kââ](((f32, f32, f32), (f32, f32, f32)), f32)) -> ((i64,
i64),
(i32,
i32,
i32))
-> *acc [kââ](((f32, f32, f32), (f32, f32, f32)), f32)

Would consume variable "potential", which is not allowed.

from the code

let associatedInteraction [n] potential box (coordinates:[n](v3,quaternion)) associations =
191     let interaction [k] (acc: *acc ([k](ft, f32)))  ((i, j), jump) : (*acc ([k](ft, f32)))
=
192         let cI = coordinates[i]
193         let cJ = triadMap f32.i32 jump |> mvMult box |> translate coordinates[j]
194         let (ftI, ftJ, p) = particleInteraction potential cI cJ
195         in write (write acc i (ftI, 0)) j (ftJ, p)
196     let ne = (zeroFT, 0)
197     let (fts, ps) = reduce_by_index_stream
198             (replicate n ne)
199             (\(ft1, p1) (ft2, p2) -> (addFT ft1 ft2, p1 + p2))
200             ne
201             interaction
202             |> unzip
203    in (fts, f32.sum ps)
potential is just a function
(I apologize for the font issues)
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
The function is intended to be equivalent to (but better performing than)
176 let associatedInteraction [n] potential box (coordinates:[n](v3,quaternion)) associations =
177     let interaction ((i, j), jump) =
178         let cI = coordinates[i]
179         let cJ = triadMap f32.i32 jump |> mvMult box |> translate coordinates[j]
180         let (ftI, ftJ, p) = particleInteraction potential cI cJ
181         in ((i, ftI), (j, ftJ), p)
182     let (ftIs, ftJs, ps) = map interaction associations |> unzip3
183     let reduction
184         = unzip
185         >-> (\(idx, fts) -> reduce_by_index
186                 (replicate n zeroFT) addFT zeroFT
187                 (map i64.i32 idx) fts)
188     in (addFTs (reduction ftIs) (reduction ftJs), f32.sum ps)
Troels Henriksen
@athas
That's probably a type checking bug. I don't get why interaction should alias potential. Maybe it will go away if you give potential an explicit type.
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
I tried giving potential a type signature, then it said the same of box, then of coordinates, but that already has a type signature.
Troels Henriksen
@athas
That's odd. Do you have a reasonably small reproducible example?
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
I have no idea how to start reducing this
it is in associations.fut in my master branch
I guess I can try to write a smaller function with less dependencies
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
205 let associatedInteractionRed [n] 'a 'b (ne:b) (add: b-> b -> b)(potential: a -> a -> b) (co
ordinates:[n]a) associations =
206     let interaction [k] (acc: *acc ([k]b)) (i, j) : (*acc ([k]b)) =
207         let cI = coordinates[i]
208         let cJ = coordinates[j]
209         let v = potential cI cJ
210         in write (write acc i v) j v
211     let fts = reduce_by_index_stream
212             (replicate n ne)
214             ne
215             interaction
216             |> unzip
217    in fts
same error
Troels Henriksen
@athas
It'll be a few days before I can take a look at it. It's probably just some oversight in alias tracking of opaque unique types (like acc), because we haven't really had any of those before.
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
Ok
Shall I make an issue?
Troels Henriksen
@athas
Sure!
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
It's rare that my bugs are acutally reducible to this degree...
Troels Henriksen
@athas
Well, ad-hoc testing like we do for the Futhark compiler is essentially a breadth-first search in the space of programs, so we have already found most bugs that can be reproduced with small programs.
But for accumulators, we haven't really tested it at all yet!
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
I'll do my best to find them!
Snektron
@snektron:matrix.org
[m]
What does accumulators entail?
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
I think it's called 'generalized reduction'.
Pretty useful for some irregular problems, and in this case, reducing one value to two indices.
the latest paper is the related one(I think).
Troels Henriksen
@athas
Well, sort of. Generalized histograms are more predictable. Generalized reductions have less structure.
@Gusten_Isfeldt_gitlab Also, be careful in general. I never finished implementing proper synchronisation for accumulator operators that cannot be implemented with hardware atomics (basically, primitive operators).
So even once the superficial type checker bug is fixed, there will be a deeper code generation bug lurking!
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
Good to know. In this case I have the function implemented already with reduce_by_index, so it'll be fairly easy to check results, to some extent anyways .
The primary problem with that implementation is that the parallel backends have monstrous memory usage
Troels Henriksen
@athas
Because you have to flatten and materialise the input/value-arrays?
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
I think that's part of it, but it also allocates memory for the processing of each element in the input array.
My backup idea for implementation would compute the input array with the stream map, to hopefully avoid this.
I hope with accumulators the computation will be fused
Snektron
@snektron:matrix.org
[m]
Is there a common file extension for futhark binary data?
Troels Henriksen
@athas
No. I use .in and .out myself, but that's admittedly a very test-centric view.
Snektron
@snektron:matrix.org
[m]
I finally finished a rough prototype for my lexer
it takes about 2.4 ms to lex a 18 MB test file - thats about 750MB/s - on an RX 580
Each lexeme is specified by some regex, and to lex it, all i need to do is a map, a scan, another map and a filter
it does require quite a large lookup table though (~2.4MB for my test lexer, which handles 12 keywords, 13 sigils, identifiers, numbers, whitespace and comments)
Some lexers i tested earlier required up to 42 MB, when entering all of C's keywords for example
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
@athas Do you have any rough estimation of when accumulators could be merged? In a couple of months? Within the year? I just don't want to build a strong dependence on features that will be highly experimental in the long term.
Troels Henriksen
@athas
@Gusten_Isfeldt_gitlab Unless we find some fundamental soundness bug in the design, likely within a month or two.
We have finally started working on the compiler features that the whole thing was meant for (AD), which will likely exercise the backend implementation enough that I will feel comfortable making it directly available to users.
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
Good, that's about what I expected.
It's nice to have some form of answer if my supervisors ask.
Troels Henriksen
@athas
I am pretty confident that the source language feature is sound, so I don't really expect any nasty surprises.
Gusten Theodor Isfeldt
@Gusten_Isfeldt_gitlab
It feels very intuitive to me, though it would be nice if you could improve on the behavior of uniqueness types used with higher order functions. Piping accumulators with |> and so on would be nice for code structure.
Troels Henriksen
@athas
I agree. It's tricky, though...
Snektron
@snektron:matrix.org
[m]
Just tested on a machine with a 2080 TI and it lexes the input file in 360us, excluding file transfers