freenode/#lisp - IRC Chatlog
Search
3:37:02
borei
im solving one problem after another, i know that constant parts of the indexes can be moved out of the loop
3:37:10
aeth
If you're doing linear algebra in pure CL, you probably want to use SBCL, though. (At least, that's the case in 2018.)
3:38:05
stacksmith
borel: keep in mind that specifying types in SBCL generates much smaller code with optimization on, but generally bigger code with it off as it treats type declarations as requests for extra checks. And of course, thinking about optimization before you need to is a sin.
3:39:04
aeth
stacksmith: But it's still generally a win for arrays and numbers because with that type check, it at least knows to use efficient, inline code instead of not-inline, type-generic code.
3:39:35
aeth
And with arrays there's the added benefit that if you have the full type information (including the dimensions) it can get rid of bounds checks
3:41:29
aeth
I think the only time you need to worry about types is with arrays, sequences, and numbers.
3:41:34
stacksmith
aeth: can't argue with that. If it matters, of course. I find more often than not that it doesn't matter because I wind up rewriting things that I care about a few times to get the algos right.
3:42:39
pierpa
for a matrix multiplication it matters, and there's not much room for algorithmic wiggles, unless he wants to go real fancy
3:43:07
aeth
It probably really depends on what you're doing. If you're working with arrays of floats, probably the most you'd have to change later (other than dimensions) is s/single-float/double-float/ or s/double-float/single-float/
3:43:52
aeth
(Although if you're really writing efficient double-float code you do sometimes have to write some hacky workarounds to avoid consing.)
3:45:57
aeth
(let ((foo (the fixnum (foobar 42)))) (+ foo 42)) is very similar (if not identical) to (let ((foo (foobar 42))) (declare (fixnum foo)) (+ foo 42)) and in either case, tells the compiler that it can assume foo is a fixnum (it can also completely ignore it, or type-check it)
3:46:25
aeth
The advantage of the is that you don't need the variable, so you can just say (+ (the fixnum (foobar 42)) 42)
3:46:50
aeth
The disadvantage is you probably want check-type instead of the or declare. It will more portably do what you probably want.
3:47:03
stacksmith
borel: Are you talking about constraining the result? Just return (the fixnum whatever). And for indices, use (the (integer 0 99) ...) or whatever the array size is...
3:47:59
stacksmith
When adding or multiplying, use (unsigned-byte ...) or (integer ..) of a bitsize that fits into a fixnum after the operation.
3:49:09
aeth
Of course, "undefined" (with the or type declarations) doesn't mean "ignore it, type check it, or assume it without checking". That just happens to be what you will probably encounter. It could also sell all of your Bitcoin or tweet it to the world if the type doesn't match. Or literally anything else that a computer can do.
3:49:31
stacksmith
Also declaring the array itself as a vector or simple-array generates much tighter code with sbcl.
3:50:45
borei
from what i read make-array will create simple-array unless you specifed :fill-pointer and/or one more parameter
3:51:21
stacksmith
borel: true enough, but I think you still need to declare it in functions that use the array.
3:53:18
aeth
You should probably use specialization-store for this. https://github.com/markcox80/specialization-store/
3:53:35
aeth
The alternative is making n versions of the exact same thing, just with different types.
3:54:34
stacksmith
Also, if you are really optimizing, you may be able to arrange the loop better using tagbody - sbcl loops sometimes jump around weirdly...
3:54:41
aeth
Or you could just inline something and hope the type information is available where it is being used. But some things produce really massive functions when disassembled, e.g. many matrix operations. So those might not be a good choice for inlining.
3:55:32
aeth
stacksmith: I'm not sure that there are many cases to use tagbody directly instead of do (do even has an implicit tagbody for when you really need it, but good luck getting that to auto-indent correctly because few people use that feature)
3:57:01
aeth
An alternative to using loops for arithmetics is to use macros to essentially loop unroll. I'm not sure how many iterations it would take before this is a bad idea. It definitely is ideal for small numbers of iterations like 2, 3, 4.
3:59:09
aeth
Oh, btw, on matrix multiplication in general: https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm
3:59:34
aeth
"Unsolved problem in computer science: What is the fastest algorithm for matrix multiplication?"
4:00:26
aeth
stacksmith: The majority of matrix libraries in CL are graphics libraries, so 4x4 matrices (and possibly smaller ones)
4:02:08
aeth
Are there many native math libraries that aren't CL graphics math libraries? Most, I think, are wrappers.
4:02:18
borei
in quantum mech - there is only matricies and vectors, and they are with complex elements
4:02:37
aeth
The Maxima CAS is interesting. It has Fortran, and it has f2cl. So I think it might compile all of its Fortran into CL!
4:04:35
aeth
In SBCL: (upgraded-array-element-type '(complex single-float)) => (complex single-float)
4:05:22
aeth
Now I think the next question is if they can be worked with in a non-consing way, just like arrays of double-floats.
4:06:52
beach
rme: Bordeaux is a great place to live, but I don't think you should come here counting on the students.
4:07:49
aeth
And it looks like it's not non-consing in SBCL: (defun foo (v) (check-type v (simple-array (complex double-float) (3))) (incf (aref v 0)) v) (disassemble #'foo)
4:09:12
aeth
By comparison: non-consing in SBCL: (defun foobar (v) (check-type v (simple-array double-float (3))) (incf (aref v 0)) v) (disassemble #'foobar)
4:09:42
stacksmith
borel: I find that when using type declarations and the... turning optimization off, sometimes generates helpful messages about dubious type declarations.
4:10:23
pjb
borei: look how slower your solution is (even with the constant subexpressions out of the loops) than indexing 2D arrays, in ccl: https://codeshare.io/2KwP3z
4:11:30
iqubic
Is there a way to take a dynamically bound string, and set it to the value of my chosing?
4:13:33
pjb
iqubic: strings may be mutable or immutable. When mutable, they may be adjustable or non adjustable. If they're not adjustabnle, then you can mutate them but not their length; if they're adjustable, you can mutate them and mutate their length. Whether the string is bound, and whether it's bound lexically od dynamically are irrelevant.
4:14:31
pjb
iqubic: notice that in general, one avoids to mutate strings, since all the difficulty is knowing whether it's an immutable or a mutable string!
4:16:20
pjb
(let ((foo (make-string 3 :initial-element #\a))) (print foo) (replace foo "bar") foo) #| "aaa" --> "bar" |#
4:17:18
pjb
borei: try it with small n and big n (eg. n=2, n=3, n=4 and n=20 n=30 n=40 and n=200, n=300, n=400).
4:17:24
aeth
borei: your matrix isn't going to be anywhere near as efficient as built-in 2D arrays because you're using CLOS
4:17:47
aeth
borei: I don't see how a hand-made matrix in CLOS is going to be more efficient than built-in matrices unless you're using a JITed CL
4:18:53
pjb
ebzzry: using a library that gives you access to x11 functions to manipulate the x11 clipboard. Hence #x11
4:22:15
pjb
stacksmith: by reading a literal indeed: '("abc" #.(vector 1 2 3) #.(make-array '(2 2) :initial-contents '((1 2) (3 4))))
4:28:15
stacksmith
pjb: re immutable arrays: What you describe seem to be just literals. SBCL will actually allow modification with a warning - not that it's a good idea. Is there something in the standard?
4:28:45
aeth
borei: (This is just my opinion.) With CL, no need to have any numbers at all. Write two equivalent ways of doing something. Then use disassemble. If the disassemblies are identical (as they often are) there is no difference. If the disassemblies are very similar, you might be able to notice the differences. Only if they're very different do you need to benchmark.
4:31:46
aeth
I would not be surprised at all if someone has already written a disassemble diff tool for this.
4:33:31
rme
I'll be in town starting on the 23rd. It'd be nice to see you if you're available sometime.
4:33:45
beach
You need to act quickly. Prices of real estate are rising fast because of the increased popularity of the city in recent years.
4:33:48
k-hos
I really do like sbcls disassmble feature, aeth, I used it the other day to confirm that macros don't have any overhead (at least simple ones)
4:34:26
aeth
k-hos: My favorite part about SBCL's disassembly is that it comments the potentially interesting things, such as constants and allocations and function calls.
4:36:04
rme
beach: From Feb. 23 through March 6th. Not sure where I'll stay; some airbnb place (or places). I'll be looking around for a place to rent for a year to start with.
4:37:21
aeth
(And I use disassembly not to write low-level code but to see how high level the code can get away with being.)
4:37:47
beach
rme: I *might* be busy until end of February. A visitor might be here. After that, I'll be available.
4:40:45
rme
Nothing beats coming to look around in person, I am thinking. Hopefully, I won't be totally priced out.
4:51:59
aeth
Bike: Should I move my length 16 array to a (4 4) array for my 4x4 matrices? You seem to know more about this than anyone else in the previous conversation.
4:52:26
aeth
It does look like SBCL can declare them dynamic extent, so they do seem to be useful enough for my uses.
4:53:48
aeth
It looks like dynamic extent still works with (list (list ...) (list ...) (list ...) (list ...)) for the initial contents (which I assume an inline make-matrix-4x4 would produce)
5:11:08
aeth
In the length 16 version it's all MOVSS, MULSS, and ADDSS. In the dimension (4 4) version, it has a lot of MOV instructions added
5:12:11
beach
borei: I suggest you introduce a variable using LET that you sum into. That way, you can declare the type of it.
5:12:47
beach
borei: It is complaining that when you use the SUM LOOP keyword, the type of the implicit variable it sums into is not known to be DOUBLE-FLOAT.
5:14:50
aeth
Bike: It's probably slightly slower, but it's really hard to tell because my computer is too fast and any loop will optimize it away
5:14:53
beach
borei: Well, you have the LOOP keyword DO at the end of the line instead of at the beginning.
5:19:24
beach
borei: You can "play with" the variables first, but you should work on the code layout before resubmitting.
5:39:26
borei
single-threaded application on the consumer-grade CPU with performance a bit less then 1Gflop on double precision numbers
5:41:28
aeth
Lisp isn't slow, but it doesn't have as many optimizations as a more popular AOT compiled language. Mainly becaue it doesn't have as many humans optimizing it as a more popular AOT compiled language.
5:41:46
aeth
But I suspect a lot of those optimizations are pointless when you're just doing linear algebra.
5:45:29
borei
i got additional and huge motivation for big dive into LISP ecosystem, huge thanks for support !
5:46:45
fiddlerwoaroof_
borei: if you're doing matrixy-stuff and have an Nvidia GPU, you might look into Gabor Melis's libraries, like mgl-mat
5:47:21
fiddlerwoaroof_
I've never got them to work because I don't have the hardware, but they look really nice for machine-learning applications
5:47:25
aeth
k-hos: Well, I think Lisp games would benefit the most from a concurrent, parallel, real-time garbage collector.
5:49:16
borei
fiddlerwoaroof_: actually i have question about ML, can you recommend any materials about ML+Lisp to read (entry level)
5:49:16
aeth
fiddlerwoaroof_: The most important part in the GC buzzwords for games is real time, afaik.
5:49:39
fiddlerwoaroof_
aeth: The built-in java GCs are really advanced, because of the JVM's position in the industry
5:49:48
aeth
Games are usually on some strict schedule (or two, if the rendering framerate is separate from the logic one). e.g. 0.01 second ticks or something.
5:51:52
fiddlerwoaroof_
borei: CL isn't the best yet for modern ML, just because we don't have the libraries that python/scala have. However, Gabor Melis managed to do pretty well using his own libraries
5:57:59
aeth
k-hos: Most games wind up using a garbage collected scripting language in addition to a non-garbage collected engine language.
5:59:33
fiddlerwoaroof_
Hmm, it looks like redhat has recently opensourced a low-latency GC: https://wiki.openjdk.java.net/display/shenandoah/Main
6:00:09
k-hos
personally I would prefer no gc and have some kind of ref counting mechanism built into the language
6:03:54
k-hos
it's pauses and inconsistency that make gcs generally bad for games, but there is little point to arguing about a theoretical language anyway
6:04:18
beach
k-hos: There are very good real-time, parallel, concurrent garbage collectors these days.
6:11:09
aeth
jackdaniel: Yes, because I think there are literally dozens of people on IRC who want one.
6:26:42
aeth
It does look like the (16) array is consistently around 2.8 kilocycles compared to the (4 4) being consistently around 3.8 kilocycles. So that is quite a drop in performance, even though I have to use SBCL's cycles to even notice it at all (0.000 seconds)
6:27:20
aeth
I've played with different ways of expressing it, e.g. pulling out all of the array accesses into variables first
6:29:00
aeth
Maybe the next thing I could try is using a loop instead of doing all of the adds/multiplies,
6:38:35
aeth
It looks like the 4x4 matrix is always slower than the fake 4x4 matrix because SBCL can't access items from it as well. It generates an extra MOV for every one or two MOVSS, which adds up a lot in matrix multiplication. Both on retrieving the values and on setting the destination matrix.
12:43:26
drmeister
Is there a way to shut down pretty printing for trace output? Or is this an implementation dependent detail?
12:44:35
Shinmera
Well, setting *print-pretty* is an option unless the implementation changes that itself during tracing.
12:48:23
scymtym
maybe implementations could add something along the lines of SB-EXT:*DEBUG-PRINT-VARIABLE-ALIST* for TRACE
12:48:58
drmeister
Sometimes in clasp trace generates pretty printed output and other times it doesn't.
12:49:27
drmeister
It's pretty much "(setq *print-pretty* <which one doesn't drmeister want right now>)"
13:01:16
drmeister
(blush) Simply (setf *print-pretty* nil) in the slime repl turns pretty printing off for trace