libera/#sicl - IRC Chatlog
Search
9:17:02
hayley
So it seems compiler hacking had some use for university classes. Today we had a class on CPUs (as part of the "computer architecture" part of the course) and they brought up CISC and RISC machines. Apparently it is easier to write a compiler for a CISC machine; it probably is, but register allocation certainly isn't easier :)
9:22:18
moon-child
though I am partial to fuzxxl's take on risc vs cisc: that the former is no longer extant
9:23:03
hayley
Apparently the textbook also states that, on average, you tend to achieve one cycle per instruction. That seems like a low bar with superscalar execution, and slightly optimistic without.
9:24:36
hayley
Henry Baker once said efficient run-time checks were harder to optimize on "untagged RISC architectures", but given that the lecturers state you need a language like C or C++ or FORTRAN to burn that well, I think it is a moot point. (:
9:26:11
hayley
We got to hear a war story about writing assembler to use both the U and V pipes on the Pentium 4 though.
9:32:53
beach
If the CISC is very regular, like the VAX, it can be a bit easier to write a compiler and to write directly in assembler.
9:34:05
beach
Also, on older CISCs, a register operation and a memory operation took rougly the same time, so there was not that issue back then.
9:37:28
hayley
Baker once wrote "Today's untagged RISC architectures put the burden on optimizing compilers to generate efficient run-time array-bounds and pointer checks", which is the only statement I had ever read suggesting compiling to a RISC was harder.
9:38:39
hayley
According to the lecturers, you still can only use C or FORTRAN to write sufficiently fast numeric code, and implementations of those languages do not do bounds checking. By that logic, there isn't anything hard about compiling to a RISC.
9:38:57
beach
So it is not the run-time checks that are optimized, but the code in general, due to the fact that more run-time checks are necessary.
9:45:33
hayley
To generate fast code. My classmates and I sometimes speak of "burning" through especially fast code.
9:46:35
hayley
ACTION is still thinking about assignment work, and hasn't yet switched contexts apparently.
9:47:43
beach
So was "well" meant to be an adverb, and "that" meant to be a relative pronoun not followed by a noun phrase?
9:48:21
hayley
If fast code can only be written in the aforementioned languages, and implementations of those languages don't perform bounds checking, then surely optimizing out bounds checks is not a large concern while writing a compiler.
9:49:32
hayley
"well" was used as an adverb, and I don't think "that" was used as a relative pronoun. It was used like "that" in "I can't ride a bicycle that well".
9:54:50
beach
We need to teach you how to write in a sufficiently unambiguous way that people like me (who require very precise phrases to get it) can understand your writing.
9:54:55
hayley
It was a strange (but predictable) thing to hear from the lecturers, given that I found my regular expression compiler (in pure Common Lisp, no SIMD trickery yet) to scan at a throughput of about 4 cycles per character.
9:56:16
beach
And in #commonlisp, you never answered my question about comparison with other programs for regular expressions. For performance I mean. I have no idea what would be considered "normal".
9:57:31
yitzi
beach: Seems like SICL has two printing packages, Incless and the mostly empty sicl-printer. Can you tell me a little bit about what is going on there. Incless defines pprint so that seems like where the pretty printer should go, but I suppose it could be put in its own package and sicl-printer fuse the two.
9:59:19
beach
It would depend a bit on how sophisticated the pretty-printer architecture needs to be.
10:00:58
beach
yitzi: My immediate reaction would be to make it a module, either in the same repository or in a separate one. Either way, I think they are fairly independent.
10:01:23
hayley
The main performance improvements are that I convert regular expressions to a DFA and compile the DFA to a single function, whereas cl-ppcre executes a chain of closures generated from a NFA, and I specialise compiled functions to array types.
10:02:09
beach
hayley: Sort of like the difference between the abandoned HIR compiler and the HIR evaluator.
10:02:15
hayley
Silly question, would there be a case for rewriting XP, like phoe did with Pitman's portable condition system, or is XP that bad?
10:03:27
beach
And I have the suspicion that it may need some facilities for client configuration, like our other libraries do.
10:07:07
hayley
I am sure my compiler could end up providing huge PROG* forms to the Common Lisp compiler if it tried to compile complex regular expressions.
10:11:26
hayley
So I've been looking into lightweight ways of cutting down code size (which have to be fast, else they might be slower than using the CL compiler for the same optimizations). One way is a modification to gilberth's derivative technique which makes "duplication" of submatch registers explicit, and avoids duplication where possible.
10:13:33
scymtym
hayley: regarding not being able to do anything about branching: pkhuong had this trick for runs of character: https://github.com/pkhuong/string-case/blob/master/string-case.lisp#L458 (link is to generated code, generator and rationale are in the same file)
10:14:24
hayley
The resulting equations for computing derivatives then sort of resemble Linear Lisp, or that sort of linear logic programming. So I call the IR "linear tagged regular expressions".
10:15:59
hayley
scymtym: Nice! I was considering something like it, as the SIMD search code would do something similar, but wasn't sure if it was a good idea. Thanks for the confirmation.
10:17:06
scymtym
hayley: sure. i don't know how applicable the technique is to unknown CHARACTER subtypes and portable code, though
10:17:43
scymtym
but i guess you could (maybe do) always compile a specific version for the CHARACTER subtype at hand
10:18:34
hayley
Right, I can see that (logxor (char-code a) (char-code b)) is not quite the same as (logxor a b). And we want the latter really.
10:19:47
hayley
I probably will generate code for each possible vector type which could store characters, but I suspect most will be SIMPLE-STRINGs.
10:32:00
hayley
It seems LLVM knows this trick, but neither I nor LLVM can think of a way to test if a character is equal to one of two other characters.
10:37:03
hayley
LLVM emits a CMP instruction, then loads the Equal flag into a register with SETE, then another CMP and SETE, then takes the logical OR of both flags. This procedure does also avoid branches though.
10:37:34
scymtym
there are two axis: simple vs. non-simple and the CHARACTER subtype. the latter determines how many characters can (at most) be tested in one step
10:39:48
scymtym
no, i don't think it is worth the effort. but you would probably have to handle different character widths anyway
10:41:15
scymtym
anyway, i'm not sure the technique is useful in your case. i just thought it might be of interest to you