freenode/#lisp - IRC Chatlog
Search
9:04:50
alandipert
aeth because ev2! mutates it.. i'm not sure the copies dominate since they're not in the hot loop (lines 36-37)
9:10:32
aeth
also, if you're sure they're always fixnum, try benchmarking with '(simple-array fixnum (*)) instead of 'simple-vector
9:11:08
alandipert
aeth the input is user-dependent, but mine is here if you want to try it: https://gist.github.com/alandipert/63e4502350d90d7b251e99cac40a3895
9:14:54
alandipert
the time to beat is 130 ms.. that's how fast a similar and type-hinted clojure algorithm does it on my machine. currently my lisp goes to ~230ms
9:18:52
beach
alandipert: Do you have to use simple vectors? It might be more efficient to use specialized vectors.
9:19:45
aeth
If you want to make a higher-order-function faster, you can usually do that by converting it into a macro, afaik.
9:20:03
alandipert
beach i don't think they have to be simple, i'm ignorant of this swath of CL :-) i went with simple because it seemed like.. the simplest
9:21:10
beach
alandipert: Well, in Common Lisp a simple vector has element type T. It might be better to use a vector type that stores numbers.
9:21:12
aeth
All I did was replaced the funcall with (progn ,@body) and now I define a function instead of passing in a higher order function. Real code should also use gensyms in macros.
9:23:22
aeth
Giving it a fixnum type doesn't make a big performance difference because fixnums are already unboxed (unlike e.g. double-float), fixnums will fit in a vector already, and it's being told they're fixnums with (the fixnum ...)
9:24:08
aeth
Even if it made no difference, though, '(simple-array fixnum (*)) in your coerce and removing the (the fixnum ...) feels more idiomatic
9:30:56
aeth
alandipert: Make sure that the length is known. That's the big thing for vectors. e.g. (declare (optimize (speed 3)) ((simple-array fixnum (1000)) code)) And use a macro instead of a higher order function, i.e. put the loop in a macro, and make the part that differs the body.
9:34:58
alandipert
aeth i can see how inlining via macro is faster, i was kind of hoping there would be a way to parameterize via defun name at least. and use (declare (inline ...))
9:35:25
alandipert
aeth https://gist.github.com/alandipert/a15a83cb49d9cabf95781b7d987bbcab is my attempt at that, no faster though
9:35:44
aeth
SBCL doesn't trust you, btw. It doesn't believe that it's not a fixnum because you're doing addition, afaik. When I disassemble, I see three object-not-fixnum-errors. If the numbers have a tighter bound than fixnum, you can save some checks each iteration of the loop (or at least, some of them might be in the loop)
9:38:45
aeth
i.e. instead of calling a function, you're inlining the whole thing into the loop iteration manually, with the macro.
9:40:00
aeth
SBCL cheats with its built-in higher order functions, and even then the cheating is a leaky abstraction and you can easily ruin performance.
9:44:58
alandipert
jdz its this clojure code, on java 9/macos, on i7 skylake https://github.com/bhauman/advent-of-clojure-2016/blob/master/src/advent_of_clojure_2017/day05.clj#L50-L59
9:52:17
aeth
And afaik you can meet the desired performance if you replace (evfun code ptr) with (progn ,@body) and redefine the functions to use this macro instead of to be passed in. Additionally, declaring it as a (simple-array fixnum (1000)) instead of * (unless it's going to be of a variable size)
9:54:05
aeth
You get a big, scary "SB-KERNEL:HAIRY-DATA-VECTOR-SET/CHECK-BOUNDS" in the disassembly without a known length, and it's every iteration of the loop because it's in ev2!
9:56:05
alandipert
jdz cool, i'll give that a look later. off to bed for now, thanks all for the help!
9:56:23
aeth
schweers: calling that function to check bounds 2000 times might have an impact in the performance if you're trying to minimize it
9:57:00
aeth
A lot of the time, it's not important. This is something that's trying to be made as fast as possible afaik.
9:59:29
aeth
Found the source: https://github.com/sbcl/sbcl/blob/7aa16ffc71fb5c04458297978292daa7f3f37dac/src/code/array.lisp
10:06:05
aeth
jdz's version gives me a consistent 0.69, which is twice as fast as the macro-ified version of ev2+run. Giving it a known length of 1000 speeds it up to about 0.64. More than I thought, but fairly insignificant. It gets rid of several bounds checks, but the bounds checks probably aren't being called every iteration anymore.
10:06:58
aeth
The macro version probably gave such a dramatic improvement because the compiler didn't have to bounds check as often.
10:09:22
aeth
known size is 2 bounds checks and 3 fixnum checks; unknown size adds 2 bounds checks; safety probably removes all the checks because the algorithm is flawless
10:12:34
alandipert
jdz your code is awesome, thanks for sharing. i like not using fancy loop stuff. ok now to bed for real :-)
10:12:36
aeth
You might be able to remove some more checks if you're clever, without resorting to safety 0. That can get you some of the way there.
10:13:37
aeth
e.g. maybe they're 32 bit signed integers? Then maybe the compiler can assume fixnum longer.
10:15:39
schweers
aeth: your measurements pretty much confirm what I suspected: bounds checks are not that expensive, since running times of programs on modern hardware are pretty much limited by the speed of memory operations.
10:19:57
aeth
Individually, the checks are pretty cheap. Collectively, they apparently add up. I don't get half the time, though. I get 0.04 seconds in the safety 0 version. And half the checks that are being removed are checks for fixnum.
10:20:57
schweers
you can go from 0.69s to 0.04s? not bad, that on the other hand is not what I expected
10:22:29
aeth
Also, that's why you should always get in the habit of putting the leading zero! 00.64 would have been obvious
10:25:50
aeth
Here's the overhead, btw: (let ((foo #(0 1 2 3 4 5 6 7))) (time (dotimes (i 10000000000) (sb-kernel:hairy-data-vector-set/check-bounds foo 4 42))))
10:29:04
aeth
Or if that's not good enough: (let ((foo (coerce (loop for i from 0 to 10000 collect i) 'simple-vector))) (time (dotimes (i 10000000000) (sb-kernel:hairy-data-vector-set/check-bounds foo 400 42))))
10:30:34
aeth
In order for it to matter, your data has to be huge or you have to have a very strict time constraint (maybe 200 frames per second?)
11:15:23
shrdlu68
When working with arrays of integers less than 128, is there a performance benefit in using :element-type '(unsigned-byte 7) rather than '(unsigned-byte 8) ?
11:17:42
schweers
according to the CMUCL manual there are (or were?) even implementations which used even worse representations in such cases
11:20:14
jmercouris
I have the following code https://gist.github.com/78247fc1030e208f023c50323d46b3e8
11:20:59
jmercouris
Additionally, the contents of "help-contents" is not actually being used within ps:ps somehow
11:23:49
schweers
if it’s a macro, and doesn’t use its argument ... on the other hand the SETF expression does use it anyway. I’m also confused
11:26:37
mercourisj
sorry, my internet keeps cutting out, I am checking the logs though, so don't worry
11:27:03
mercourisj
from the project description: "The ps macro takes Parenscript code in the form of lists (Parenscript code and Common Lisp code share the same representation), translates as much as it can into constant JavaScript strings at macro-expansion time, and expands into a form that will evaluate to a string containing JavaScript code."
11:31:34
jmercouris
Whereas it should look like "document.body.innerHTML = "contents of help-contents variable";"
11:36:04
schweers
shrdlu68: As far as I know this cannot be done. I wish there was a way though. Or rather I wish this could happen automatically.
11:37:15
schweers
jmercouris: can you verify that SETF has any effect? Also, have you tried factoring the (PS:PS ...) expression into a function and calling that with HELP-CONTENTS as an argument?
11:38:46
jmercouris
schweers: I haven't tried that, but I don't see how that would help, I didn't write ps:ps it is part of parenscript
11:39:40
schweers
I know, but I don’t know anything about parenscript, so I have no idea what the macro actually does.
11:39:42
mercourisj
schweers: setf most definitely has an effect, if you look at the outputted html it has an assignment on the innerhtml of the body
11:43:44
jmercouris
schweers: Correct, it must be in JS the point is to set the text of the web page
11:44:18
jmercouris
schweers: Correct, it must be in JS the point is to set the text of the web page
11:50:54
mercourisj
If you look in the reference here:https://common-lisp.net/project/parenscript/reference.html
11:51:14
mercourisj
You'll see the section "Symbol Conversion" which is what is happening with the value of help-contents, rather than an eval to its value
11:54:09
jmercouris
alright, so reading the manual again, I retried ps:lisp, apparently ONLY at runtime does the lisp form get evaluated, so I was doing the macro expansion and it looked wrong to me, but did actually work
11:54:41
jmercouris
so to anyone reading the log in the future, the following is how I solved my problem (ps:lisp help-contents) instead of just using help-contents which was being translated to a js symbol helpContents
12:02:16
Bike
if you know it's an (unsigned-byte 7) you might as well tell the implementation so, since it upgrades regardless
12:03:12
Devon
(ps:lisp '(upgraded-array-element-type '(unsigned-byte 7))) => (UPGRADED-ARRAY-ELEMENT-TYPE '(UNSIGNED-BYTE 7))
12:05:40
jdz
I wrote a bit about arrays ages ago here: http://t-b-o-g.blogspot.com/2009/10/brians-brain-on-common-lisp-take-2.html </shameless-plug>
12:23:13
schweers
jdz: but does it have any benefit declaring the element type as (unsigned-byte 7)?
12:23:47
schweers
now that I think of it: there may be cases in which the compiler can prove that an operation on an element will not be larger than (unsigned-byte 8)
12:27:56
schweers
but I may very well be wrong about that, I’m not old enough to remember a time when a byte wasn’t 8 bits
12:29:02
jdz
I remember at least some architectures from early lisp days had 36-bit words, which I think implied 9-bit bytes.
12:35:19
jdz
I also remember reading about strings being chunks of 5? characters (each one 7-bits) packed in words?
12:41:57
jdz
Oh, this might be it (from IBM_704 page): «Alphanumeric characters were usually 6-bit BCD, packed six to a word.»
12:45:56
Devon
PDP-10 SIXBIT for filenames, SQUOZE for symbol tables, 7-bit ASCII for text, 8-bit SAIL for terminal output, 9-bit... not sure but I'm sure it got some use.
13:19:33
pjb
Well, foremost, the character set was determined by the printer chains. They could easily be changed for each printing job!
14:54:35
tfb
jdz: Symbolics L & G machines were 32 + 4 tag for data, 28 + 8 tag for address. Ivory was 32 + 8 tag for data and I think the same for address
17:46:02
circ-user-81lkm
Is it possible to query a "system class" like character for its subclasses? e.g. http://www.lispworks.com/documentation/HyperSpec/Body/t_ch.htm#character has base-char and extended-char extending character. Something like (subclasses 'character) => '(base-char extended-char)?
17:47:14
Shinmera
You can't query class relationship information in CL at all, you need the MOP for that.
17:48:40
emaczen
There is even a library called closer-mop which will work on most implementations too
17:48:41
_death
types aren't necessarily classes, in particular base-char and extended-char are not classes
17:50:28
Shinmera
If you know the set of concrete types you can probe with subtypep, I guess, but not in general.
17:51:49
Bike
if you need to do it programmatically (and as i recall, you're making some kind of editor) it's implementation specific. Look through swank
17:52:17
Bike
and what you'll get is a source location, not the actual source form, which has probably been discarded
17:52:30
_death
jmercouris: there is no way in plain common lisp.. pjb has a package called ibcl which may be appropriate
17:53:00
circ-user-81lkm
Well I saw a demo somewhere of a UI that produced a class hierarchy diagram and it included character and it's subtypes but I'm not sure how it produced that
17:53:18
jmercouris
Maybe I'm just re-inventing emacs at this point, perhaps I shouldn't implement that
17:53:49
Bike
It's true, though, if you want to do editor things you could do worse than just bringing in swank rather than reimplementing it
17:54:19
jmercouris
Yeah, maybe it is pointless though, because someone can just use slime to connect to my program
17:55:16
jmercouris
I should just get slime working with my standalone executable, and avoid too many things like "jump to source" and stuff like that, I'll leave it at showing docstrings for built in help
18:07:12
sjl
jmercouris: embed swank in the browser process, let people connect to and interact with it with whatever editor they want
18:08:14
jmercouris
sjl: Yeah, I have a branch for that, I was so close to releasing it, but none of the GUI updates were making it on screen
18:10:17
jmercouris
It doesn't make sense to me how that is even possible that the updates were not happening on screen, because all of the functions that update the gui have a (on-main-thread) macro which calls them in the ccl event process
18:11:29
circ-user-81lkm
Thanks for the MOP tip - I think this is what I'm after, e.g. (closer-mop:class-direct-subclasses (find-class 'character)) => (#<BUILT-IN-CLASS STANDARD-CHAR>)
18:11:31
emaczen
What does no more immobile pages left mean? It is an error I get from SBCL and then I get sent to LDB?
18:14:14
Bike
Whether they are types with elements in them is orthogonal to whether they are classes
18:28:15
pjb
I've noticed that with the latest versions of macOS, if you try to draw in a timer, it doesn't work reliably, even though you configure the time to execute on the main thread.
19:14:51
earl-ducaine
<possibly spam> Lispinators! I'd like to do a series of blog posts on MOP that provides enough practicle information and examples to alow someone get get started using it on real world problems (something that I found to be lacking either on the Internet or in the published literature.)
19:15:06
earl-ducaine
I'm collecting feedback to guage interest and collect ideas. Feel free to reply here on IRC or post a comment to my blog post requesting the same: https://wordpress.com/view/earlducaine.wordpress.com
19:20:44
Bike
earl-ducaine: this might not be what you had in mind, but the word wrap is weird https://i.imgur.com/3U7UPFn.png
19:23:02
earl-ducaine
Damn. That's what you get for composing a Wordpress first in Emacs. Looked great on my screen with, probably because of exactly alined linebreaks.
19:24:10
Bike
earl-ducaine: i think the discussion of slots is a bit confusing. objects still 'own' slots in clos
19:24:51
Bike
it might be worthwhile to be kind of anal about the distinction between slots (parts of an object, probably anonymous in a vector) and slot definitions
19:27:22
Bike
as structuring goes i'd use examples. like some basic features someone want: persistence, observers. stuff you can implement in a simple way in a page or so while introducing mop concepts
19:31:16
Bike
AMOP isn't good as a textbook of how to use MOP because it's definitely intended as a book on developing MOP instead
19:32:05
whoman
that makes sense.. i read it the other day; was not sure if it was a preview, or a booklet/pamphlette, ..
19:32:37
whoman
but MOP is awesome! isn't it? we can defclass with not-yet-defined subclasses (forward) and...
19:33:34
whoman
...my sense of OOP is directly tied to syntax, of which CLOS looks like everything else, so i am reserving its application currently. its all just lists anyhow.
19:44:50
whoman
ok earl-ducaine i read it all. my summary: its an introduction to the MOP book, as it talks mostly about it, so i was thinking about that book, and now at the end, after reading it, i feel like i am hungrier than when i came to dinner. i would have the impression that MOP is mysterious undocumented internal assembly unsafe scariness
19:56:49
Xach
borodust: should i expect to see a difference in the scaling issue today with the latest dist update?
20:01:57
Xach
It would basically show what you've seen before - 1/4 scaling in the lower left of the window
20:09:39
Ober
Shinmera: emacs right? was looking to see if you could enable command-frequency, as very curious which slime functions I'm not making use of. you do a lot of stuff where it's not obvious to me which method you invoked
20:15:30
Shinmera
Other than that the standard paredit things, plus multiple-cursors and expand-region are commands I frequently use.