I am working on a parser generator tool (a replacement for SmaCC) and
one of the things I a m interested in is the direct translation of language specifications into the virtual machine code (SmaCC and my current version of it use Squeak as the target language). One of the problems I have is that, for some languages, the natural translation into VM code uses computed gotos. There are two scenarios here: 1) goto X where X is a variable. 2) goto (coll at: y) where coll is a Collection. For example, one such language is that of regular expressions, which I wish to translate into finite state machines implemented in VM code. In this case I need case 2) gotos where coll is a collection of associations, possibly a Dictionary. I also plan to write a debugger for this (and other languages) but that is another story. I realize that the Cog VM is being built for Smalltalk (Squeak? Pharo?) for which the goto instructions are not needed and thus I assume unavailable. But there is something to viewing a virtual machine as general purpose and thus the target of multiple languages as is the case for the Java virtual machine. If the Cog VM is viewed this way then I argue there is a need for my goto instructions because some languages have need for them. For example, many languages have case statements. (I am all for object oriented but I would be willing to accept a case statement in Smalltalk too; the Squeak code implemented one in Squeak doesn't cut it). Anyway, I am not arguing to Change Squeak or Smalltalk but I am arguing to have my goto instructions in Cog VM. Is there any chance of this????? I don't know the Squeak VM or the Cog VM either but I assume these instructions don't exist because I see no need of them when the source language is Squeak or any version of Smalltalk for that matter. I also assume that there is already a full list of 256 instructions in the Cog VM and thus no room for my goto instructions unless some instructions are removed. Are there Cog VM instructions that are so rarely used that they could be removed without unreasonably slowing down the Cog VM interpretation of byte codes generated from Squeak source code????? I accept that it will always be that almost all byte codes to be interpreted by the Cog VM are generated from Smalltalk source. Good luck with the Cog VM. I look forward to seeing it used in Squeak/Pharo. Ralph Boland |
On Sat, 1 Nov 2014, Ralph Boland wrote: (No quote, sorry) The current Squeak bytecode set contains various jump intructions, which are variants of goto, but none of them are dynamic. The sole instruction you'd need is a modified jumpTo: which jumps to the value found on the top of the stack instead of a value encoded in the bytecode. Let's call it jumpToTop. With this new instruction you could compile goto X to a variable push and jumpToTop. It would also cover your other variant - goto (coll at: y) - by pushing coll and y, sending #at:, and finally jumpToTop. You can create a custom VM with a new bytecode set (one which includes jumpToTop), the same way the NewSpeak VM is built. Levente |
In reply to this post by Ralph Boland
Hi Ralph,
On Sat, Nov 1, 2014 at 1:37 PM, Ralph Boland <[hidden email]> wrote:
First, a different approach than compiling to Smalltalk is to compile to a parse tree. We do this in the pseudo JavaScript compiler we've implemented at Cadence, translating an AST into a Squeak compiler parse tree for code generation. Targeting a parse tree gives you much more freedom; you can express things that aren't expressible in Smalltalk. And if you target bytecodes you can do even more.
Off the top of my head one could - map to perform: using some mangled selector. Yes this is problematic because one has to split the scope between the two methods, so in general it's not a solution - map to a case statement, which is what Squeak does. Just map it to a sequence of compare and branches. Or better still, to a binary tree. Coincidentally this is used by the JIT to implement block dispatch in methods that contain more than one block. I know of other VM implementations using it for PIC dispatch with really good performance. - use thisContext pc: value. This /should/ be fine in the stack VM, but slooooow in the JIT because internally mapping bytecode pcs to machine code pcs is slow, and currently slower still because the frame will be converted to a pure context and then converted back into a frame on the return from pc:. But this solution isn't to be rejected out-of-hand. It can be optimized to avoid the frame conversion and the JIT might be able to optimize it. The main problem is the compiler has no support for labels so there would be work here.
The Cog VMs support multiple bytecode sets. If you look at the BytecodeSets package on VMMaker you can read the class comments of the BytecodeEncoder subclasses such as EncoderForSistaV1. These bytecode sets have a few more unused bytecodes. This multiple bytecode set support is better implemented in Spur where there is only one compiled method header format and support for 64k literals. So let me encourage you to move to Spur and to look at the Sista set. The class comment of each encoder class specifies the instruction set it targets.
and welcome to vm-dev! best,
Eliot |
In reply to this post by Ralph Boland
>> >> I am working on a parser generator tool (a replacement for SmaCC) and >> one of the things I a m interested in is the direct translation of >> language specifications into the virtual machine code (SmaCC and my >> current version of it use Squeak as the target language). >> > First, a different approach than compiling to Smalltalk is to compile to a > parse tree. We do this in the pseudo JavaScript compiler we've implemented > at Cadence, translating an AST into a Squeak compiler parse tree for code > generation. Targeting a parse tree gives you much more freedom; you can > express things that aren't expressible in Smalltalk. And if you target > bytecodes you can do even more. I never considered using a parse tree as the target. An interesting idea which in many instances may be the best approach. But for my regular expression example I would still want to generate byte codes. In any case I wouldn't want to restrict users of my parser generator tool to any one of the three options (Smalltalk code, parse tree, byte code). It is my responsibility to make all three options as easy and efficient as reasonably possible for users of the parser generator tool. Haven't put much thought into this yet though. So far Smalltalk (Squeak) is the only option. >> One of the problems I have is that, for some languages, the natural >> translation >> into VM code uses computed gotos. >> There are two scenarios here: >> >> 1) goto X where X is a variable. >> 2) goto (coll at: y) where coll is a Collection. >> > There are several ways of implementing this without computed bytecodes in > the instruction set, but there is also the possibility of implementing it > directly in the instruction set. > Off the top of my head one could > - map to perform: using some mangled selector. Yes this is problematic > because one has to split the scope between the two methods, so in general > it's not a solution Doesn't appeal to me. > - map to a case statement, which is what Squeak does. Just map it to a > sequence of compare and branches. Or better still, to a binary tree. > Coincidentally this is used by the JIT to implement block dispatch in > methods that contain more than one block. I know of other VM > implementations using it for PIC dispatch with really good performance. I don't know what you mean my Squeak mapping to a case statement since there is no case statement in Squeak/Smalltalk and I can't off hand think of where one is needed (some Squeak users might feel they need one but that is a different matter). The use of compare and branches might be OK in some cases but a mess for the finite state machines generated from regular expressions. Actually, even with computed gotos FSMs are somewhat messy but without them it's worse. I don't know what 'PIC dispatch' is. To use a binary tree don't I need some kind of computed goto for when I reach a leaf of the tree???? > - use thisContext pc: value. This would be a possibility for me to experiment with for now. When I have a working parser generator tool I could campaign for my computed goto instructions to be added to the VM. > This /should/ be fine in the stack VM, but > slooooow in the JIT because internally mapping bytecode pcs to machine code > pcs is slow, and currently slower still because the frame will be converted > to a pure context and then converted back into a frame on the return from > pc:. But this solution isn't to be rejected out-of-hand. It can be > optimized to avoid the frame conversion and the JIT might be able to > optimize it. I assume that if computed gotos were used the translation to machine code would require a direct mapping of (virtually labeled) bytecode locations to machine code locations. I think this can be done in a reasonable amount of time but others such as yourself clearly understand the issues far better than I do. The dirty solution to start would be to simply not JIT the code that uses computed gotos. > The main problem is the compiler has no support for labels so > there would be work here. I don't mind doing the work but to my way of thinking "goto X" is pretty basic and is thus best handled at the VM/byte code level. Anything else is doing in a complicated way something that is fairly simple. Of course changing the VM/byte codes by even a single byte code is a major deal unless done when the VM/byte codes are initially created. Alas I must deal with what already exists. Even so, my preference is to work with the VM if at all possible. >> For example, one such language is that of regular expressions, which I >> wish to translate into finite state machines implemented in VM code. >> In this case I need case 2) gotos where coll is a collection of >> associations, possibly a >> Dictionary. I also plan to write a debugger for this (and other languages) >> but that is another story. >> >> I realize that the Cog VM is being built for Smalltalk (Squeak? Pharo?) >> for which the goto instructions are not needed and thus I assume >> unavailable. But there is something to >> viewing a virtual machine as general purpose and thus the target of >> multiple languages as is >> the case for the Java virtual machine. >> If the Cog VM is viewed this way then I argue there is a need for my goto >> instructions >> because some languages have need for them. >> For example, many languages have case statements. (I am all for object >> oriented >> but I would be willing to accept a case statement in Smalltalk too; the >> Squeak code >> implemented one in Squeak doesn't cut it). > > I've occasionally thought about this for many years. A computed jump might > be nice. Eg index an Array literal of pcs with the integer on top of > stack, falling through on bad type or out of range. This is the way I am thinking. If there are other reasons for a computed jumpTo as well all the better. > Anyway, I am not arguing to Change Squeak or Smalltalk but I am arguing > to have my goto instructions in Cog VM. Is there any chance of this????? > There's no chance of me spending time implementing this any time soon. I have too much high-priority tasks to tackle this. But I want to encourage you or others to have a go implementing it. It's fun! I understand and am willing to be the one to add one or more computed jump instructions, including working on the JIT code generator if needed. As you say it should be fun (and also educational). But 1) I am pretty busy now too and probably won't get to this for a year. 2) If I am to do this it would be great if someone can write a specification as to what is to be done. If someone can write this now that would be great but if they write it when I post that I am ready to do the work that would also be fine. 3) I don't want to just have my own private VM/byte codes. I want users of my parser generator tool to be able to load it into a standard version of Squeak and run it there including the possible generation of compilers for compiling their domain specific language programs into byte codes if desired. >> I don't know the Squeak VM or the Cog VM either but I assume these >> instructions don't exist because I see no need of them when the source >> language is >> Squeak or any version of Smalltalk for that matter. I also assume that >> there is already >> a full list of 256 instructions in the Cog VM and thus no room for my goto >> instructions >> unless some instructions are removed. >> >> Are there Cog VM instructions that are so rarely used that they could be >> removed without >> unreasonably slowing down the Cog VM interpretation of byte codes >> generated from Squeak source code????? >> > The current set has 3 unused bytecodes, one of which Spur uses, so > effectively there are two unused bytecodes. Levente Uzonyi in his posting pointed out that only one instruction is needed. I don't like having to push the address to jump to onto the stack, preferring a byte code with an argument, but I could live with his solution if that is what is decided. In the case of goto coll at: X the address is likely to end up on top of the stack anyway so Levente's jumpToTop instruction looks good in any case. > The Cog VMs support multiple bytecode sets. If you look at the > BytecodeSets package on VMMaker you can read the class comments of the > BytecodeEncoder subclasses such as EncoderForSistaV1. These bytecode sets > have a few more unused bytecodes. This multiple bytecode set support is > better implemented in Spur where there is only one compiled method header > format and support for 64k literals. So let me encourage you to move to > Spur and to look at the Sista set. The class comment of each encoder class > specifies the instruction set it targets. I am prepared to work with Spur and the Sista set. I am looking for someone to say that if I do this work that incorporating the work into Spur will be seriously considered. Ralph Boland |
Is this a request for a jump table? (switch statement in C) 2014-11-03 2:48 GMT-03:00 Ralph Boland <[hidden email]>:
|
In reply to this post by Ralph Boland
Hi Ralph,
On Sun, Nov 2, 2014 at 9:48 PM, Ralph Boland <[hidden email]> wrote:
But there is. And it is very convenient when one doesn't want to spread a case over different classes, or when the cases distribute over values of the same class (e.g. integer values). People often claim that a case statement isn't necessary because one has polymorphism, but unless the language supports singletons (which of course Smalltalk does not) a case statement is much more readable than e.g. an if-then-else tree or a "Dictionary mapping values to blocks or selectors" solution. Since you're unaware of the case statement I suggest you browse senders of caseOf: and caseOf:otherwise: in Squeak trunk (which includes selectors of optimized selectors that end up not being sent) or caseError, which is sent when there's no otherwise clause. Here's an example: menuHook: aMenu named: aSymbol shifted: aBool "Enhance aMenu with registered services." aSymbol caseOf: { [ #classListMenu ] -> [ ServiceGui browser: self classMenu: aMenu ]. [ #codePaneMenu ] -> [ ServiceGui browser: self codePaneMenu: aMenu ]. [ #messageCategoryMenu] -> [ ServiceGui browser: self messageCategoryMenu: aMenu ]. [ #messageListMenu ] -> [ ServiceGui browser: self messageListMenu: aMenu ]. [ #systemCategoryMenu ] -> [ ServiceGui browser: self classCategoryMenu: aMenu ] } otherwise: [ "do nothing" ] This compiles down to a sequence of comparisons.
Polymorphic inline cache dispatch. In JIT VMs such as Cog polymorphic send sites are optimized using jump tables, one jump for each class encountered at the send site, up tio some small limit such as 6 cases. Right now in Cog these jump tables are sequential comparisons. But in some VMs, where the degree of polymorphism may be much higher (think prototype languages such as JavaScript) a binary tree may be much miore efficient, if harder to organize.
No. Once you're at the leaf you just include the bytecodes. So for example take the following case statement: quickPrimitiveGeneratorFor: aQuickPrimitiveIndex <api> <returnTypeC: 'int (*quickPrimitiveGeneratorFor(sqInt aQuickPrimitiveIndex))(void)'> ^aQuickPrimitiveIndex caseOf: { [256] -> [#genQuickReturnSelf]. [257] -> [#genQuickReturnConstNil]. [258] -> [#genQuickReturnConstTrue]. [259] -> [#genQuickReturnConstFalse]. [260] -> [#genQuickReturnConstMinusOne]. [261] -> [#genQuickReturnConstZero]. [262] -> [#genQuickReturnConstOne]. [263] -> [#genQuickReturnConstTwo] } otherwise: [#genQuickReturnInstVar] This is compiled in the current Squeak compiler as 61 <10> pushTemp: 0 62 <88> dup 63 <2A> pushConstant: 256 64 <B6> send: = 65 <9B> jumpFalse: 70 66 <87> pop 67 <29> pushConstant: #genQuickReturnSelf 68 <A4 35> jumpTo: 123 70 <88> dup 71 <28> pushConstant: 257 72 <B6> send: = 73 <9B> jumpFalse: 78 74 <87> pop 75 <21> pushConstant: #genQuickReturnConstNil 76 <A4 2D> jumpTo: 123 ... 117 <22> pushConstant: 263 118 <B6> send: = 119 <99> jumpFalse: 122 120 <21> pushConstant: #genQuickReturnConstTwo 121 <90> jumpTo: 123 122 <20> pushConstant: #genQuickReturnInstVar 123 <7C> returnTop but it could be more efficient if the code were pushTemp: 0 dup pushConstant: 256 send: < jumpFalse: L1 dup pushConstant: 260 send: < jumpFalse: L2 dup pushConstant: 258 send: < jumpFalse: L3 dup pushConstant: 257 send: < jumpFalse: L4 pushConstant: #genQuickReturnSelf jumpTo: L0 pushConstant: #genQuickReturnConstNil jumpTo: L0 ... L1: pushConstant: #genQuickReturnInstVar L0: returnTop
Yes, it could be. The JIT would generate a jump table from the literal containing the bytecoded pcs, and there would be no conversion; only indexing the jump table and jumping. Again, organizing that table as a binary switch may well be faster on modern architectures. Indirect jumps typically involve pipeline stalls, whereas binary jump trees don't.
Sure. Get back to me when you're ready to work on it and I'll write the specification, and help you with whatever info you need. There should be room in the bytecode sets we'll likely be using next year.
If the bytecode is one that takes an integer on top of stack, and an Array literal containing bytecode pcs, falling through on out of range, then nothing other than the index need be pushed on top of stack. That would be my preference.
I can say that, yes. I will seriously consider adding it. I think its a useful thing in the bytecode set, precisely to allow compiling other languages to the VM.
best,
Eliot |
On Mon, Nov 3, 2014 at 11:34 AM, Eliot Miranda <[hidden email]> wrote:
I think Levante's suggestion for jumpToTop was just to take the pc from the top of the stack, with no indirection through an Array literal. Then jumping to a pc in an array would be - push the array - push the index of the pc you want - send #at: - jumpToTop -Colin |
On Mon, Nov 3, 2014 at 1:11 PM, Colin Putney <[hidden email]> wrote:
Right, and that doesn't play well with the JIT because conversion would be required and that's slow. If one goes with teh explicit jump table in an Array literal a) compilation is likely easier because one doesn't have to know the pc when generating the switch code b) it plays well with teh JIT since the jit can convert the bytecode pcs to machine code pcs at compile-time, not run-time. In any case one can play the stack top game as an experiment using thisContext pc:, no need for a bytecode. But the bytecode should use the literal approach for the reasons stated.
best,
Eliot |
In reply to this post by Ralph Boland
Hi Ralph,
On Tue, Nov 4, 2014 at 9:09 PM, Ralph Boland <[hidden email]> wrote:
So what's a "true" case statement? For me, at least, the Squeak one *is*, and is more general than one limited to purely integer keys, as for example is C's switch statement. A number of languages provide case statements that are like Squeak's. What do you consider a "true" case statement?
You keep on saying it doesn't have one. I disagree.
Nah. One should always be able to map it down somehow. Tis will be easier with the Spur instruction set which lifts number of literals and length of branches limits.
Great, thanks!!
Yes, but getting to the limit of what the VM can reasonably interpret. Better would be an Array of value. pc pairs, where the keys are the values the switch bytecode compares top of stack against, and the pcs are where to jump to on a match. The JIT can therefore implement the table as it sees fit, whereas the interpreter can just do a linear search through the Array.
Yes. Generate bad bytecode and the VM crashes.
Same. Once the tool is generating correct bytecode the VM should stop crashing ;-)
You're welcome.
best,
Eliot |
In reply to this post by Ralph Boland
> Hi Ralph, I mean that: caseOf: is not part of the language itself but rather part of the... > > > > I was aware of caseOf: in Squeak. I always found it awkward to use and > > felt a true case statement would be simpler. Alas, it's impossible to > > have a true case statement added to Smalltalk now I think. > So what's a "true" case statement? For me, at least, the Squeak one *is*, > and is more general than one limited to purely integer keys, as for example > is C's switch statement. A number of languages provide case statements > that are like Squeak's. What do you consider a "true" case statement? standard library or set of packages that one finds in the IDE. To be part of the language it would need to be something the compiler is aware of. That is to day the Smalltalk language is not very much. Smalltalk (Squeak) the language would not include Sets or Dictionaries but would include (some) Array classes because some aspects of Arrays are dealt with directly by the compiler. Selectors such as ifTrue: and to:do: are part of the language because they are inlined by the compiler. Put another way, if I could get my doBlockAt: method incorporated into the Squeak IDE it would nevertheless NOT be part of Squeak the language. The consequence of caseOf: not being part of the language is that the compiler/VM cannot perform optimizations when caseOf: is run into but must treat it as user written code. Squeak's caseOf: is more general than C's switch statement but it could be more general in that there is a hard coded message (=). I would like to be able to replace the '=' message by an arbitrary binary operator such as includes: or '>'. I have to backtrack here: I looked at the code and it looks like the compiler inlines caseOf: and caseOf:otherwise. If so then these selectors are part of the language by my definition. ... > > But I wouldn't want to be forced to implement my FSMs this way. > > It might be acceptable for small FSMs. > > I want to avoid sequential search and > > even binary search might be rather expensive. > > I look at computed gotos as the solution but, > > as you pointed out, computed gotos pose problems for JIT. > > Admittedly, for large FSM's, it might be best or necessary to > > use a FSM simulator anyway, as I do now. > Nah. One should always be able to map it down somehow. Tis will be easier > with the Spur instruction set which lifts number of literals and length of > branches limits. Good to hear. > > Again, for my FSM, case this would often be considered to be good. > > But if the state transition tables are sparse then Dictionaries > > might be preferable to Arrays. > > Yes, but getting to the limit of what the VM can reasonably interpret. > Better would be an Array of value. pc pairs, where the keys are the values > the switch bytecode compares top of stack against, and the pcs are where to > jump to on a match. The JIT can therefore implement the table as it sees > fit, whereas the interpreter can just do a linear search through the Array. I am looking at this from the point of view of a compiler writer/generator and consider your proposal as inadequate for my needs. You, I think, are looking at this from the point of view of a VM writer and what can reasonably be delivered. I don't think what I want is overly difficult for the interpreter to deliver but as you pointed out, and you know much better than I, what I want causes serious problems for the VM. > > My expection is that at: be sent to the collection object > > to get the address to go to. Knowing that the collection > > is an array though makes it easier for the compiler/VM to > > ensure that the addresses stored in the collection are valid. > > Actually, the compiler will be generating the addresses. > > Does the VM have absolute trust in the compiler to generate valid > > addresses? > Yes. Generate bad bytecode and the VM crashes. This is what I expected to hear but wanted it to be clear for compilers generated by my parser generator tool as you did. Ralph |
On Sat, Nov 8, 2014 at 11:21 AM, Ralph Boland <[hidden email]> wrote:
Ah OK. I see what you mean. But you're wrong on a few counts. First, there are *no* control structures in the language beyond closures and polymorphism. ifTrue:, to:do:, and: whileTrue: et al are all defined in the library, not by the compiler. Second, tehse structures, /including/ caseOf: are understood by the compiler and compiled to non-message-sending code. So none of the blocks in caseOf:, ifTrue: and: whileTrue: et al, the optimized selectors, are created and all are inlined by the compiler. So a) by your criterion of being in the compiler caseOf: is in the language, but b) it all control structures in Smalltalk are defined in the library, and some are optimized by the compiler.
There is a syntactic form for creating Array, but really the notion that the Smalltalk compiler defines the language is a limited one. It's fair to say that language is defined by a small set of variables, return, blocks, an object representation (ability to create classes that define a sequence of named inst vars and inherit from other classes), and message lookup rules (normal sends and super sends), and a small number of literal forms (Array, Integer, Float, Fraction, ByteArray, String and Symbol literals), and a method syntax. The rest is in the library. What this really means is that Smalltalk can't be reduced to a language, becaue the anguage doesn't defne enough. Instead it is a small language and a large library.
No. One can change the compiler to not inline them. This is merely an optimization.
Well, live and learn :-)
best,
Eliot |
Eliot Miranda wrote: > > > > ------------------------------------------------------------------------ > > > > On Sat, Nov 8, 2014 at 11:21 AM, Ralph Boland <[hidden email] > <mailto:[hidden email]>> wrote: > > > > Hi Ralph, > ... > > > > > > > I was aware of caseOf: in Squeak. I always found it awkward to > use and > > > felt a true case statement would be simpler. Alas, it's > impossible to > > > have a true case statement added to Smalltalk now I think. > > > So what's a "true" case statement? For me, at least, the Squeak > one *is*, > > and is more general than one limited to purely integer keys, as > for example > > is C's switch statement. A number of languages provide case > statements > > that are like Squeak's. What do you consider a "true" case > statement? > > I mean that: caseOf: is not part of the language itself but rather > part of the > standard library or set of packages that one finds in the IDE. To > be part of the > language it would need to be something the compiler is aware of. > > > Ah OK. I see what you mean. But you're wrong on a few counts. First, > there are *no* control structures in the language beyond closures and > polymorphism. ifTrue:, to:do:, and: whileTrue: et al are all defined in > the library, not by the compiler. Second, tehse structures, /including/ > caseOf: are understood by the compiler and compiled to > non-message-sending code. So none of the blocks in caseOf:, ifTrue: > and: whileTrue: et al, the optimized selectors, are created and all are > inlined by the compiler. So a) by your criterion of being in the > compiler caseOf: is in the language, but b) it all control structures in > Smalltalk are defined in the library, and some are optimized by the > compiler. Reviewing the code for the following is enlightening: True>ifTrue: True>>ifFalse: False>>ifTrue: False>>ifFalse: to see as the original implementation, but remembering that as an optimization these are inlined, so that code is currently not executed. Eliot, Would I be right to presume that the Interpreter does execute those methods without optimisation? cheers -ben > > That is to > day the Smalltalk language is not very much. Smalltalk (Squeak) the > language > would not include Sets or Dictionaries but would include (some) > Array classes > because some aspects of Arrays are dealt with directly by the compiler. > > > There is a syntactic form for creating Array, but really the notion that > the Smalltalk compiler defines the language is a limited one. It's fair > to say that language is defined by a small set of variables, return, > blocks, an object representation (ability to create classes that define > a sequence of named inst vars and inherit from other classes), and > message lookup rules (normal sends and super sends), and a small number > of literal forms (Array, Integer, Float, Fraction, ByteArray, String and > Symbol literals), and a method syntax. The rest is in the library. > What this really means is that Smalltalk can't be reduced to a language, > becaue the anguage doesn't defne enough. Instead it is a small language > and a large library. > > Selectors such as ifTrue: and to:do: are part of the language > because they are inlined by the compiler. > > > No. One can change the compiler to not inline them. This is merely an > optimization. > > > Put another way, if I could get my doBlockAt: method incorporated > into the Squeak IDE > it would nevertheless NOT be part of Squeak the language. > The consequence of caseOf: not being part of the language is that > the compiler/VM > cannot perform optimizations when caseOf: is run into but must > treat it as > user written code. > > Squeak's caseOf: is more general than C's switch statement but it > could be more > general in that there is a hard coded message (=). I would like to > be able to replace > the '=' message by an arbitrary binary operator such as includes: > or '>'. > > I have to backtrack here: I looked at the code and it looks like > the compiler inlines > caseOf: and caseOf:otherwise. If so then these selectors are part > of the language > by my definition. > > > Well, live and learn :-) > > > > ... > > > > But I wouldn't want to be forced to implement my FSMs this way. > > > It might be acceptable for small FSMs. > > > I want to avoid sequential search and > > > even binary search might be rather expensive. > > > I look at computed gotos as the solution but, > > > as you pointed out, computed gotos pose problems for JIT. > > > Admittedly, for large FSM's, it might be best or necessary to > > > use a FSM simulator anyway, as I do now. > > > > Nah. One should always be able to map it down somehow. Tis will > be easier > > with the Spur instruction set which lifts number of literals and > length of > > branches limits. > > Good to hear. > > > > > Again, for my FSM, case this would often be considered to be good. > > > But if the state transition tables are sparse then Dictionaries > > > might be preferable to Arrays. > > > > > Yes, but getting to the limit of what the VM can reasonably > interpret. > > Better would be an Array of value. pc pairs, where the keys are > the values > > the switch bytecode compares top of stack against, and the pcs > are where to > > jump to on a match. The JIT can therefore implement the table as > it sees > > fit, whereas the interpreter can just do a linear search through > the Array. > > I am looking at this from the point of view of a compiler > writer/generator and consider > your proposal as inadequate for my needs. You, I think, are looking > at this from > the point of view of a VM writer and what can reasonably be > delivered. I don't think > what I want is overly difficult for the interpreter to deliver but > as you pointed out, > and you know much better than I, what I want causes serious problems > for the VM. > > > > My expection is that at: be sent to the collection object > > > to get the address to go to. Knowing that the collection > > > is an array though makes it easier for the compiler/VM to > > > ensure that the addresses stored in the collection are valid. > > > Actually, the compiler will be generating the addresses. > > > Does the VM have absolute trust in the compiler to generate valid > > > addresses? > > > > Yes. Generate bad bytecode and the VM crashes. > > This is what I expected to hear but wanted it to be clear for > compilers generated > by my parser generator tool as you did. > > Ralph > > > > > -- > best, > Eliot |
Hi Ben, On Nov 8, 2014, at 3:35 PM, Ben Coman <[hidden email]> wrote: > Eliot Miranda wrote: >> ------------------------------------------------------------------------ >> On Sat, Nov 8, 2014 at 11:21 AM, Ralph Boland <[hidden email] <mailto:[hidden email]>> wrote: >> > Hi Ralph, >> ... >> > > >> > > I was aware of caseOf: in Squeak. I always found it awkward to >> use and >> > > felt a true case statement would be simpler. Alas, it's >> impossible to >> > > have a true case statement added to Smalltalk now I think. >> > So what's a "true" case statement? For me, at least, the Squeak >> one *is*, >> > and is more general than one limited to purely integer keys, as >> for example >> > is C's switch statement. A number of languages provide case >> statements >> > that are like Squeak's. What do you consider a "true" case >> statement? >> I mean that: caseOf: is not part of the language itself but rather >> part of the >> standard library or set of packages that one finds in the IDE. To >> be part of the >> language it would need to be something the compiler is aware of. Ah OK. I see what you mean. But you're wrong on a few counts. First, there are *no* control structures in the language beyond closures and polymorphism. ifTrue:, to:do:, and: whileTrue: et al are all defined in the library, not by the compiler. Second, tehse structures, /including/ caseOf: are understood by the compiler and compiled to non-message-sending code. So none of the blocks in caseOf:, ifTrue: and: whileTrue: et al, the optimized selectors, are created and all are inlined by the compiler. So a) by your criterion of being in the compiler caseOf: is in the language, but b) it all control structures in Smalltalk are defined in the library, and some are optimized by the compiler. > > Reviewing the code for the following is enlightening: > True>ifTrue: > True>>ifFalse: > False>>ifTrue: > False>>ifFalse: > to see as the original implementation, but remembering that as an optimization these are inlined, so that code is currently not executed. > > Eliot, Would I be right to presume that the Interpreter does execute those methods without optimisation? The interpreter directly executes the bytecode produced by the compiler. Go look. So it depends in how the code base is compiled. Right now the interpreter does *not* , because inlined blocks, conditional branches and jumps are much faster than closure creation and messages. The interpreter benefits a lot from this; early Smalltalk implementations were interpreted hence the optimisation in the first place. However, with adaptive optimisation one can allow the JIT to perform the optimisation in context, allowing alternative implementations of ifTrue: et al in other than booleans. In Sista we've chosen not to do that, keeping inlining and using conditional branches as our performance counters. But it may allow the compiler to be smart and optimize these forms in fewer cases. > > cheers -ben > >> That is to >> day the Smalltalk language is not very much. Smalltalk (Squeak) the >> language >> would not include Sets or Dictionaries but would include (some) >> Array classes >> because some aspects of Arrays are dealt with directly by the compiler. >> There is a syntactic form for creating Array, but really the notion that the Smalltalk compiler defines the language is a limited one. It's fair to say that language is defined by a small set of variables, return, blocks, an object representation (ability to create classes that define a sequence of named inst vars and inherit from other classes), and message lookup rules (normal sends and super sends), and a small number of literal forms (Array, Integer, Float, Fraction, ByteArray, String and Symbol literals), and a method syntax. The rest is in the library. What this really means is that Smalltalk can't be reduced to a language, becaue the anguage doesn't defne enough. Instead it is a small language and a large library. >> Selectors such as ifTrue: and to:do: are part of the language >> because they are inlined by the compiler. >> No. One can change the compiler to not inline them. This is merely an optimization. >> Put another way, if I could get my doBlockAt: method incorporated >> into the Squeak IDE >> it would nevertheless NOT be part of Squeak the language. >> The consequence of caseOf: not being part of the language is that >> the compiler/VM >> cannot perform optimizations when caseOf: is run into but must >> treat it as >> user written code. >> Squeak's caseOf: is more general than C's switch statement but it >> could be more >> general in that there is a hard coded message (=). I would like to >> be able to replace >> the '=' message by an arbitrary binary operator such as includes: or '>'. >> I have to backtrack here: I looked at the code and it looks like >> the compiler inlines >> caseOf: and caseOf:otherwise. If so then these selectors are part >> of the language >> by my definition. >> Well, live and learn :-) >> ... >> > > But I wouldn't want to be forced to implement my FSMs this way. >> > > It might be acceptable for small FSMs. >> > > I want to avoid sequential search and >> > > even binary search might be rather expensive. >> > > I look at computed gotos as the solution but, >> > > as you pointed out, computed gotos pose problems for JIT. >> > > Admittedly, for large FSM's, it might be best or necessary to >> > > use a FSM simulator anyway, as I do now. >> > Nah. One should always be able to map it down somehow. Tis will >> be easier >> > with the Spur instruction set which lifts number of literals and >> length of >> > branches limits. >> Good to hear. >> > > Again, for my FSM, case this would often be considered to be good. >> > > But if the state transition tables are sparse then Dictionaries >> > > might be preferable to Arrays. >> > >> > Yes, but getting to the limit of what the VM can reasonably >> interpret. >> > Better would be an Array of value. pc pairs, where the keys are >> the values >> > the switch bytecode compares top of stack against, and the pcs >> are where to >> > jump to on a match. The JIT can therefore implement the table as >> it sees >> > fit, whereas the interpreter can just do a linear search through >> the Array. >> I am looking at this from the point of view of a compiler >> writer/generator and consider >> your proposal as inadequate for my needs. You, I think, are looking >> at this from >> the point of view of a VM writer and what can reasonably be >> delivered. I don't think >> what I want is overly difficult for the interpreter to deliver but >> as you pointed out, >> and you know much better than I, what I want causes serious problems >> for the VM. >> > > My expection is that at: be sent to the collection object >> > > to get the address to go to. Knowing that the collection >> > > is an array though makes it easier for the compiler/VM to >> > > ensure that the addresses stored in the collection are valid. >> > > Actually, the compiler will be generating the addresses. >> > > Does the VM have absolute trust in the compiler to generate valid >> > > addresses? >> > Yes. Generate bad bytecode and the VM crashes. >> This is what I expected to hear but wanted it to be clear for >> compilers generated >> by my parser generator tool as you did. >> Ralph >> -- >> best, >> Eliot > |
Eliot Miranda wrote: > > Hi Ben, > > On Nov 8, 2014, at 3:35 PM, Ben Coman <[hidden email]> wrote: > >> Eliot Miranda wrote: >>> ------------------------------------------------------------------------ >>> On Sat, Nov 8, 2014 at 11:21 AM, Ralph Boland <[hidden email] <mailto:[hidden email]>> wrote: >>> > Hi Ralph, >>> ... >>> > > >>> > > I was aware of caseOf: in Squeak. I always found it awkward to >>> use and >>> > > felt a true case statement would be simpler. Alas, it's >>> impossible to >>> > > have a true case statement added to Smalltalk now I think. >>> > So what's a "true" case statement? For me, at least, the Squeak >>> one *is*, >>> > and is more general than one limited to purely integer keys, as >>> for example >>> > is C's switch statement. A number of languages provide case >>> statements >>> > that are like Squeak's. What do you consider a "true" case >>> statement? >>> I mean that: caseOf: is not part of the language itself but rather >>> part of the >>> standard library or set of packages that one finds in the IDE. To >>> be part of the >>> language it would need to be something the compiler is aware of. Ah OK. I see what you mean. But you're wrong on a few counts. First, there are *no* control structures in the language beyond closures and polymorphism. ifTrue:, to:do:, and: whileTrue: et al are all defined in the library, not by the compiler. Second, tehse structures, /including/ caseOf: are understood by the compiler and compiled to non-message-sending code. So none of the blocks in caseOf:, ifTrue: and: whileTrue: et al, the optimized selectors, are created and all are inlined by the compiler. So a) by your criterion of being in the compiler caseOf: is in the language, but b) it all control structures in Smalltalk are defined in the library, and some are optimized by the compiler. >> Reviewing the code for the following is enlightening: >> True>ifTrue: >> True>>ifFalse: >> False>>ifTrue: >> False>>ifFalse: >> to see as the original implementation, but remembering that as an optimization these are inlined, so that code is currently not executed. >> >> Eliot, Would I be right to presume that the Interpreter does execute those methods without optimisation? > > The interpreter directly executes the bytecode produced by the compiler. Go look. So it depends in how the code base is compiled. Right now the interpreter does *not* , because inlined blocks, conditional branches and jumps are much faster than closure creation and messages. The interpreter benefits a lot from this; early Smalltalk implementations were interpreted hence the optimisation in the first place. However, with adaptive optimisation one can allow the JIT to perform the optimisation in context, allowing alternative implementations of ifTrue: et al in other than booleans. In Sista we've chosen not to do that, keeping inlining and using conditional branches as our performance counters. But it may allow the compiler to be smart and optimize these forms in fewer cases. > Ahh. I was thinking about it the wrong way. To check.. inlined means inlined-bytecode not inlined-machine-code? And the result of compilation is the same bytecode to run on the VM regardless of whether that VM is the Intepreter or Cog ? (And indeed the compiler is itself running in-image on top of the VM). cheers -ben > >> cheers -ben >> >>> That is to >>> day the Smalltalk language is not very much. Smalltalk (Squeak) the >>> language >>> would not include Sets or Dictionaries but would include (some) >>> Array classes >>> because some aspects of Arrays are dealt with directly by the compiler. >>> There is a syntactic form for creating Array, but really the notion that the Smalltalk compiler defines the language is a limited one. It's fair to say that language is defined by a small set of variables, return, blocks, an object representation (ability to create classes that define a sequence of named inst vars and inherit from other classes), and message lookup rules (normal sends and super sends), and a small number of literal forms (Array, Integer, Float, Fraction, ByteArray, String and Symbol literals), and a method syntax. The rest is in the library. What this really means is that Smalltalk can't be reduced to a language, becaue the anguage doesn't defne enough. Instead it is a small language and a large library. >>> Selectors such as ifTrue: and to:do: are part of the language >>> because they are inlined by the compiler. >>> No. One can change the compiler to not inline them. This is merely an optimization. >>> Put another way, if I could get my doBlockAt: method incorporated >>> into the Squeak IDE >>> it would nevertheless NOT be part of Squeak the language. >>> The consequence of caseOf: not being part of the language is that >>> the compiler/VM >>> cannot perform optimizations when caseOf: is run into but must >>> treat it as >>> user written code. >>> Squeak's caseOf: is more general than C's switch statement but it >>> could be more >>> general in that there is a hard coded message (=). I would like to >>> be able to replace >>> the '=' message by an arbitrary binary operator such as includes: or '>'. >>> I have to backtrack here: I looked at the code and it looks like >>> the compiler inlines >>> caseOf: and caseOf:otherwise. If so then these selectors are part >>> of the language >>> by my definition. >>> Well, live and learn :-) >>> ... >>> > > But I wouldn't want to be forced to implement my FSMs this way. >>> > > It might be acceptable for small FSMs. >>> > > I want to avoid sequential search and >>> > > even binary search might be rather expensive. >>> > > I look at computed gotos as the solution but, >>> > > as you pointed out, computed gotos pose problems for JIT. >>> > > Admittedly, for large FSM's, it might be best or necessary to >>> > > use a FSM simulator anyway, as I do now. >>> > Nah. One should always be able to map it down somehow. Tis will >>> be easier >>> > with the Spur instruction set which lifts number of literals and >>> length of >>> > branches limits. >>> Good to hear. >>> > > Again, for my FSM, case this would often be considered to be good. >>> > > But if the state transition tables are sparse then Dictionaries >>> > > might be preferable to Arrays. >>> > >>> > Yes, but getting to the limit of what the VM can reasonably >>> interpret. >>> > Better would be an Array of value. pc pairs, where the keys are >>> the values >>> > the switch bytecode compares top of stack against, and the pcs >>> are where to >>> > jump to on a match. The JIT can therefore implement the table as >>> it sees >>> > fit, whereas the interpreter can just do a linear search through >>> the Array. >>> I am looking at this from the point of view of a compiler >>> writer/generator and consider >>> your proposal as inadequate for my needs. You, I think, are looking >>> at this from >>> the point of view of a VM writer and what can reasonably be >>> delivered. I don't think >>> what I want is overly difficult for the interpreter to deliver but >>> as you pointed out, >>> and you know much better than I, what I want causes serious problems >>> for the VM. >>> > > My expection is that at: be sent to the collection object >>> > > to get the address to go to. Knowing that the collection >>> > > is an array though makes it easier for the compiler/VM to >>> > > ensure that the addresses stored in the collection are valid. >>> > > Actually, the compiler will be generating the addresses. >>> > > Does the VM have absolute trust in the compiler to generate valid >>> > > addresses? >>> > Yes. Generate bad bytecode and the VM crashes. >>> This is what I expected to hear but wanted it to be clear for >>> compilers generated >>> by my parser generator tool as you did. >>> Ralph >>> -- >>> best, >>> Eliot > |
Hi Ben! On Nov 8, 2014, at 4:20 PM, Ben Coman <[hidden email]> wrote: > Eliot Miranda wrote: >> Hi Ben, >> On Nov 8, 2014, at 3:35 PM, Ben Coman <[hidden email]> wrote: >>> Eliot Miranda wrote: >>>> ------------------------------------------------------------------------ >>>> On Sat, Nov 8, 2014 at 11:21 AM, Ralph Boland <[hidden email] <mailto:[hidden email]>> wrote: >>>> > Hi Ralph, >>>> ... >>>> > > >>>> > > I was aware of caseOf: in Squeak. I always found it awkward to >>>> use and >>>> > > felt a true case statement would be simpler. Alas, it's >>>> impossible to >>>> > > have a true case statement added to Smalltalk now I think. >>>> > So what's a "true" case statement? For me, at least, the Squeak >>>> one *is*, >>>> > and is more general than one limited to purely integer keys, as >>>> for example >>>> > is C's switch statement. A number of languages provide case >>>> statements >>>> > that are like Squeak's. What do you consider a "true" case >>>> statement? >>>> I mean that: caseOf: is not part of the language itself but rather >>>> part of the >>>> standard library or set of packages that one finds in the IDE. To >>>> be part of the >>>> language it would need to be something the compiler is aware of. Ah OK. I see what you mean. But you're wrong on a few counts. First, there are *no* control structures in the language beyond closures and polymorphism. ifTrue:, to:do:, and: whileTrue: et al are all defined in the library, not by the compiler. Second, tehse structures, /including/ caseOf: are understood by the compiler and compiled to non-message-sending code. So none of the blocks in caseOf:, ifTrue: and: whileTrue: et al, the optimized selectors, are created and all are inlined by the compiler. So a) by your criterion of being in the compiler caseOf: is in the language, but b) it all control structures in Smalltalk are defined in the library, and some are optimized by the compiler. >>> Reviewing the code for the following is enlightening: >>> True>ifTrue: >>> True>>ifFalse: >>> False>>ifTrue: >>> False>>ifFalse: >>> to see as the original implementation, but remembering that as an optimization these are inlined, so that code is currently not executed. >>> >>> Eliot, Would I be right to presume that the Interpreter does execute those methods without optimisation? >> The interpreter directly executes the bytecode produced by the compiler. Go look. So it depends in how the code base is compiled. Right now the interpreter does *not* , because inlined blocks, conditional branches and jumps are much faster than closure creation and messages. The interpreter benefits a lot from this; early Smalltalk implementations were interpreted hence the optimisation in the first place. However, with adaptive optimisation one can allow the JIT to perform the optimisation in context, allowing alternative implementations of ifTrue: et al in other than booleans. In Sista we've chosen not to do that, keeping inlining and using conditional branches as our performance counters. But it may allow the compiler to be smart and optimize these forms in fewer cases. > > Ahh. I was thinking about it the wrong way. To check.. inlined means inlined-bytecode not inlined-machine-code? And the result of compilation is the same bytecode to run on the VM regardless of whether that VM is the Intepreter or Cog ? Exactly. > (And indeed the compiler is itself running in-image on top of the VM). > cheers -ben Right. And in Sista even the adaptive optimizer runs in-image whereas in almost every other adaptive optimizing/speculative inlining VM the optimizer is in-VM. >>> cheers -ben >>> >>>> That is to >>>> day the Smalltalk language is not very much. Smalltalk (Squeak) the >>>> language >>>> would not include Sets or Dictionaries but would include (some) >>>> Array classes >>>> because some aspects of Arrays are dealt with directly by the compiler. >>>> There is a syntactic form for creating Array, but really the notion that the Smalltalk compiler defines the language is a limited one. It's fair to say that language is defined by a small set of variables, return, blocks, an object representation (ability to create classes that define a sequence of named inst vars and inherit from other classes), and message lookup rules (normal sends and super sends), and a small number of literal forms (Array, Integer, Float, Fraction, ByteArray, String and Symbol literals), and a method syntax. The rest is in the library. What this really means is that Smalltalk can't be reduced to a language, becaue the anguage doesn't defne enough. Instead it is a small language and a large library. >>>> Selectors such as ifTrue: and to:do: are part of the language >>>> because they are inlined by the compiler. >>>> No. One can change the compiler to not inline them. This is merely an optimization. >>>> Put another way, if I could get my doBlockAt: method incorporated >>>> into the Squeak IDE >>>> it would nevertheless NOT be part of Squeak the language. >>>> The consequence of caseOf: not being part of the language is that >>>> the compiler/VM >>>> cannot perform optimizations when caseOf: is run into but must >>>> treat it as >>>> user written code. >>>> Squeak's caseOf: is more general than C's switch statement but it >>>> could be more >>>> general in that there is a hard coded message (=). I would like to >>>> be able to replace >>>> the '=' message by an arbitrary binary operator such as includes: or '>'. >>>> I have to backtrack here: I looked at the code and it looks like >>>> the compiler inlines >>>> caseOf: and caseOf:otherwise. If so then these selectors are part >>>> of the language >>>> by my definition. >>>> Well, live and learn :-) >>>> ... >>>> > > But I wouldn't want to be forced to implement my FSMs this way. >>>> > > It might be acceptable for small FSMs. >>>> > > I want to avoid sequential search and >>>> > > even binary search might be rather expensive. >>>> > > I look at computed gotos as the solution but, >>>> > > as you pointed out, computed gotos pose problems for JIT. >>>> > > Admittedly, for large FSM's, it might be best or necessary to >>>> > > use a FSM simulator anyway, as I do now. >>>> > Nah. One should always be able to map it down somehow. Tis will >>>> be easier >>>> > with the Spur instruction set which lifts number of literals and >>>> length of >>>> > branches limits. >>>> Good to hear. >>>> > > Again, for my FSM, case this would often be considered to be good. >>>> > > But if the state transition tables are sparse then Dictionaries >>>> > > might be preferable to Arrays. >>>> > >>>> > Yes, but getting to the limit of what the VM can reasonably >>>> interpret. >>>> > Better would be an Array of value. pc pairs, where the keys are >>>> the values >>>> > the switch bytecode compares top of stack against, and the pcs >>>> are where to >>>> > jump to on a match. The JIT can therefore implement the table as >>>> it sees >>>> > fit, whereas the interpreter can just do a linear search through >>>> the Array. >>>> I am looking at this from the point of view of a compiler >>>> writer/generator and consider >>>> your proposal as inadequate for my needs. You, I think, are looking >>>> at this from >>>> the point of view of a VM writer and what can reasonably be >>>> delivered. I don't think >>>> what I want is overly difficult for the interpreter to deliver but >>>> as you pointed out, >>>> and you know much better than I, what I want causes serious problems >>>> for the VM. >>>> > > My expection is that at: be sent to the collection object >>>> > > to get the address to go to. Knowing that the collection >>>> > > is an array though makes it easier for the compiler/VM to >>>> > > ensure that the addresses stored in the collection are valid. >>>> > > Actually, the compiler will be generating the addresses. >>>> > > Does the VM have absolute trust in the compiler to generate valid >>>> > > addresses? >>>> > Yes. Generate bad bytecode and the VM crashes. >>>> This is what I expected to hear but wanted it to be clear for >>>> compilers generated >>>> by my parser generator tool as you did. >>>> Ralph >>>> -- >>>> best, >>>> Eliot Eliot (phone) |
Free forum by Nabble | Edit this page |