libera/commonlisp - IRC Chatlog
Search
5:05:46
specbot
Tilde Left-Bracket: Conditional Expression: http://www.lispworks.com/reference/HyperSpec/Body/22_cgb.htm
7:19:10
TimoT
Morning. Is there a limit on the size of the case statement in CL? I have a case where macros generate relatively large statements (hundreds of cases) and SBCL chokes.
7:20:04
pjb
TimoT: theorically, none. In practice, the compiler will probably have a hard time if it has to generate a code vector bigger than array-total-size-limit or the available memory.
7:20:42
TimoT
In this case SBCL runs out of the control stack at 200+ statements, which seems low to me.
7:23:01
TimoT
I ran into this while converting some Vulkan headers to sb-alien and Vulkan uses enums to get more type safety over define constants. For example, the structure type tag is an enum and there are a few hundred structs in Vulkan at present.
7:24:07
TimoT
Digging into the SBCL source it seems that enums are implemented as either a plist or simple vector, but conversion from an enum tag is a large ecase.
7:31:47
TimoT
Unless the compiler can actually optimize the ecase expression lookup, it's going to be slow as well. Perhaps for large enums a hash table or some tree lookup would be more appropriate.
8:10:58
beach
TimoT: Did you check the SBCL documentation to see whether it is possible to increase the stack size when you start the SBCL process?
8:12:21
beach
TimoT: Also, we don't use the term "statement" for that purpose. We usually refer to them as "form"s. There are only a few places in the standard where a form is considered a "statement". One is in a TAGBODY, but I forget the others.
8:12:44
TimoT
Yes it is possible. It seems weird to me though that the standard stack size would not be able to compile a case of 256.
8:13:35
TimoT
It seems though that the case lookup is optimized using symbol hashes (code/macros.lisp).
8:29:57
Shinmera
There's still chatter about it here, but you're more likely to stir up useful discussion in the right channel, since maintainers don't read all of this channel.
8:30:13
beach
TimoT: The CASE operator in Common Lisp is restricted so that keys are not evaluated, and so that the comparison can be EQ or EQL. This restrictions allows the compiler to optimize it in various ways.
8:33:03
TimoT
beach: Yes. I'm now reading the SBCL implementation, which as mentioned appears to use sxhash to split the keys into buckets, but there are various special cases. It's a bit hairy.
8:42:29
beach
Right. Since all the keys are available at compile time, it is possible to do perfect hashing and things like that.
8:43:46
_death
TimoT: but do you really need a CASE there? code is generated both for the dispatch and the body forms.. but if there are hundreds of clauses, the forms in each clause are probably similar, may not need to be duplicated
8:46:09
TimoT
_death: No, a case is not necessary. It's just that a straightforward conversion of C enum -> sb:alien enum hits this problem. I was thinking of hacking the translator to produce some alternative solution (not sb-alien:enum) to avoid being stuck here. It's a hobby project.
8:47:43
TimoT
I have a very old (10 years give or take) piece of code that used to go from gcc-xml to sb-alien, I just quickly updated it to use cast-xml. I guess nowadays using clang directly would be the way to go for these.
8:48:31
_death
TimoT: as a macro writer you need to think about generated code size.. with CASE there's also the issue of a potentially linear scan.. wouldn't a simple function that performs the dispatch like (funcall (get-associated-function x)) work?
8:49:45
TimoT
_death: The macro in question here is actually from SBCL's sb-alien implementation, so how SBCL implements code for C style enums.
8:59:37
Shinmera
cl-opengl definitely has enums that have that many or more keys and that works fine.
9:03:38
TimoT
Shinmera: There's also some sort of vulkan binding in cl-vulkan. I don't know how up to date it is though. Doesn't matter that much for this use case as I'm mostly interested in embedding some compute stuff in CL.
14:11:18
rdrg109_
I was going to answer with more questions about your answer, but I was ln a solved the root problem, so there was no need to answer the question I asked.