Cryptographic Primitives

On 5-Oct-06, at 8:29 AM, Ron Teitelbaum wrote:

> All,
>
>
>
> We are considering adding a few more Cryptographic Primitives.

Ron, all you need to do is split out the plugin changes you need and  
send them to me; assuming I can understand the code well enough to  
feel it is safe I will add it to the next release of VMMaker. Is this  
a new plugin, or are you wanting to expend an existing one?

Any in-image code needs to be separately considered by whoever is  
going to handle integration. I suggest you make thre mantis reports
a) one to cover 'adding crypto wotsits'
b) one for crypo VM changes - relate it to a and assign it to me
c) one for image changes - relate it to a and hope that someone will  
wave their hand to say they are the harvester
Then when both b & c are resolved you will know that a is finished. I  
like hierarchical work reports.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
Useful Latin Phrases:- Fac ut vivas. = Get a life.

Thanks Tim the process sounds fine but before we go to the effort I would
like to know if there is a consensus that this is a good thing to do.  

Do you agree it is a worthwhile effort and a reasonable goal to include
these little primitives internally in the distributed VM's?

> Tim:
> Is this
> a new plugin, or are you wanting to expend an existing one?

I would like to have the DESPlugin which is already a part of the VMMaker
compiled internally in the distributed VM's, and we are considering writing
others to speed up implementations.

Ron

On 5-Oct-06, at 9:05 AM, Ron Teitelbaum wrote:

> Thanks Tim the process sounds fine but before we go to the effort I  
> would
> like to know if there is a consensus that this is a good thing to do.

Well that's definitely not for me to decide; I think it's perfectly  
sensible to make them available within the VMMaker world and that  
would leave it up to you (as in all you out there) to discuss the rest.

I'm puzzled by your use of 'internally' in two places - indicating  
that you think it important. Internal, external, it makes no  
difference to vmmaker stuff and no programmatic difference to anyone  
else. As far as I can recall, the general habit of vm building for  
most platforms is to include pretty much all the plugins in the  
distribution download, and to have most of those compiled internally.

On windows for example this is largely a user convenience matter  
because apparently windows users can't cope with more than one file.  
On OSX, the application bundle means there is no particular advantage  
either way. On *nix I have no idea because I simply haven't used it  
in along time. Unix users probably want the plugins to be kernel  
extensions with cryptic names.


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
when people are free to do as they please, they usually imitate each  
other

For me internal means that there is no additional dll file that the VM has
to communicate with.  Running the plugin in the general vm allocated memory
has some security advantages.  (once we secure the vm)

Ron

I'll note if the plugin is external then the plugin support people  
can lobby to include it in the plugins
distributed on a platform, then update as they see fit by working  
with the website/ftp folks. Otherwise
for internal ones they have to get the VM builder involved to build a  
new VM which takes yet another level of coordination and another  
person involved in the process of having all the right files,  
fiddling with build environments, updating the VM SVN tree etc.  
Which Tim rightly points out doesn't gain any benefits anyway.

This is not to say that I won't occasionally build  external plugins  
for folks that haven't the required sofware/hardware or expertise of  
course.  Oh and $$ is always acceptable as a bribe.


On 5-Oct-06, at 10:34 AM, tim Rowledge wrote:

--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

> This is not to say that I won't occasionally build  external plugins
> for folks that haven't the required sofware/hardware or expertise of
> course.  Oh and $$ is always acceptable as a bribe.

     I'll do it for half of whatever he's asking. ;)


-C

--
Craig Latta
http://netjam.org/resume

tim Rowledge wrote:
>
> On 5-Oct-06, at 9:05 AM, Ron Teitelbaum wrote:
>
>> Thanks Tim the process sounds fine but before we go to the effort I would
>> like to know if there is a consensus that this is a good thing to do.
>
> Well that's definitely not for me to decide; I think it's perfectly
> sensible to make them available within the VMMaker world and that would
> leave it up to you (as in all you out there) to discuss the rest.

I'm +1 on the idea. The crypto prims are algorithms that are typically
chosen to execute in 32bit and we pay a heavy price running them inside
Squeak. Having primitified some myself (MD5 and RC4 in Croquet to be
precise) speedups of a 100x are typical (which I have previously only
seen for floating point code, not for integer heavy code). In addition,
crypto prims are tiny bits of inner loops - I'd be extremely surprised
if the difference in compiled VM code is anywhere near 50k or so.

Given the tradeoffs and the importance for Crypto in many application
domains, it seems like a good choice to include these primitives directly.

BTW, while we're at it: In Croquet, I've added a primitive to gather
entropy from the OS for seeding crypto RNGs securely; if the current
Crypto prims don't include that I would heavily lobby for including it -
  while it's not difficult to write platform specific versions, having a
common abstraction over the vastly different means (a file on Unix, and
API call on Windows) is definitely helpful.


Cheers,
   - Andreas

so go for them...

> BTW, while we're at it: In Croquet, I've added a primitive to  
> gather entropy

what is that?
entropy from the OS sounds like a fun concept.

Stef

Andreas,

Thank you for your support.  As for the entropy collector. I'll take as many
as you have, do you have 31 more?  I've been considering writing Schneier's
Fortuna for our PRNG.  

Ron

Ron Teitelbaum wrote:
> Thank you for your support.  As for the entropy collector. I'll take as many
> as you have, do you have 31 more?  I've been considering writing Schneier's
> Fortuna for our PRNG.  

The primitive just hooks up to /dev/urandom on Unix machines and to
RtlGenRandom() on Windows.

Cheers,
   - Andreas

What is the difference between the DESPlugin and the pure smalltalk DES code
that was provided.

Also it would be interesting to hear Bryce's input on this.  Speeding up now
is good, but if the JIT turns out fast (as it sounds like it will) then we
would want as much as possible to be pure smalltalk, no?

Hi J J,

DESPlugin is faster, but we haven't done any real tests to figure out how
much slower the native smalltalk version is.  Des in general is a fast
algorithm.  3Des is 3 times slower.  Form what I understand the native
version is acceptable for performance.  Other things like SHA256 are fine
for hashing small values, but we found the difference between SHA1 and
SHA256 hashing 1 million a's is pretty significant.  We expect SHA256 to be
slower but since I having written the plugin for it the difference is SHA1
is subsecond and SHA256 takes 38 seconds.  This would be unacceptable
performance for and TLS1.2 ciphersuites.  So a plugin is needed.
 
>
> Also it would be interesting to hear Bryce's input on this.  Speeding up
> now
> is good, but if the JIT turns out fast (as it sounds like it will) then we
> would want as much as possible to be pure smalltalk, no?
>

I would be interested in the answer.

Ron Teitelbaum

J J wrote:
> Also it would be interesting to hear Bryce's input on this.  Speeding up
> now is good, but if the JIT turns out fast (as it sounds like it will)
> then we would want as much as possible to be pure smalltalk, no?

No. First, Exupery is not a JIT. Second, it is not yet in a state where
it can be used for serious production projects. Third, having a plugin
doesn't mean you can't have a pure smalltalk version - in fact the pure
smalltalk version would be the default isn't available. Therefore,
adding the primitives doesn't take anything away, all it does is add
some very significant speed benefits.

Cheers,
   - Andreas

I had been told it was.  In this list actually.

>Second, it is not yet in a state where it can be used for serious
>production projects.

Right.  Which is why I said "Speeding up now is good".

>Third, having a plugin doesn't mean you can't have a pure smalltalk version
>- in fact the pure smalltalk version would be the default isn't available.
>Therefore, adding the primitives doesn't take anything away, all it does is
>add some very significant speed benefits.
>
>Cheers,
>   - Andreas

Well it sounds like a big win then.

J J wrote:
>> No. First, Exupery is not a JIT.
>
> I had been told it was.  In this list actually.

Yeah, it's quite confusing actually. I found the statement that
"[Exupery is] a "JIT" for Squeak that doesn't compile just in time"
which (to me) makes no sense as "JIT" stands for "just in time" so how
could a JIT not compile just in time? ;-)

Cheers,
   - Andreas

J J writes:
 > Also it would be interesting to hear Bryce's input on this.  Speeding up now
 > is good, but if the JIT turns out fast (as it sounds like it will) then we
 > would want as much as possible to be pure smalltalk, no?

For now, if you've got a demonstratable need for speed write a
plugin. Exupery is not yet ready for production use.

I've a few ideas that should allow Smalltalk to run at the same speed
as C for both floating point and 32 bit integer work. The general case
needs SSA based optimisation which is years away. However there's an
interesting special case that could be implemented now.

The cost for both floating point calculation and 32 bit integer work
is object creation.

In the expression:

   x := a + b + c + d

You only really need to create one object to hold the result. To
optimise this you just need to know that a, b, and c are floats (or 32
bit integers). This can be read from the polymorphic inline
caches. Exupery does this now to optimise #at: and #at:put: for
different types. Then you need to remove the redundant conversions
into Squeak floats (boxing) then back into machine floats (unboxing).
The removal can be done by a simple tree travesal, there's a little
bit of complexity in case "a" is ever something other than a float.
Exupery does this to remove the overhead of booleans in expressions
such as "a < 10 ifTrue: [...]".

To optimise the use of floats or 32 bit integers inside a statement
you need to be able to dynamically inline primitives and to do simple
optimisations involving tree traversals. Exupery does both of these
now. What's missing is an implementation of either floating point
values or 32 bit integers for Exupery.

So removing the overhead for floats and 32 bit integers inside
statements is easy. Removing it across statements is harder. That
requires proper program analysis. That unfortunately will involve
waiting for Exupery 3.0.

I'm interested in Hans-Martin's Squeak implementation of DES in Squeak
as something to look at compiling. However for now I'm focussing on
regular code.

Bryce

Andreas Raab writes:
 > J J wrote:
 > >> No. First, Exupery is not a JIT.
 > >
 > > I had been told it was.  In this list actually.
 >
 > Yeah, it's quite confusing actually. I found the statement that
 > "[Exupery is] a "JIT" for Squeak that doesn't compile just in time"
 > which (to me) makes no sense as "JIT" stands for "just in time" so how
 > could a JIT not compile just in time? ;-)

When Exupery is running in a background thread a user shouldn't
notice that it's not a "real" JIT. So calling it a JIT is fair.

It does not stop execution to compile like the VisualWorks VM does.
This means it must fall back to the interpreter if compiled code
doesn't exist. It can't compile "just" in time. It can compile just
afterwards though.


I'll write an up to date overview of what Exupery is, what it plans to
be, and what it does now soon. Either before or just after the next
release.

All that's left to do before releasing is implement the two primitives
#new and #@ then fix some bugs. The two primitives are required for
the largeExplorers benchmark.

Here's the current benchmarks.

  arithmaticLoopBenchmark 1395 compiled   91 ratio: 15.330
  bytecodeBenchmark       2132 compiled  456 ratio:  4.675
  sendBenchmark           1588 compiled  684 ratio:  2.322
  doLoopsBenchmark        1086 compiled  649 ratio:  1.673
  largeExplorers           337 compiled  366 ratio:  0.921
  compilerBenchmark        794 compiled  767 ratio:  1.035
  Cumulative Time         4241 compiled 1389 ratio   3.053

The most interesting benchmarks now are largeExplores (opening a very
large explorer) and compilerBenchmark (compiling a large method into
bytecodes). Both are real uses. Both use a profiler to choose methods
to compile then PIC based type feedback to inline primitives.

largeExplorers needs a faster #@. The interpreter inlines this into a
bytecode while Exupery is currently doing a full message send. Once
it's implemented as a compiled primitive it will then get inlined
automatically.

compilerBenchmark is spending 5% of it's time in compiled code and
support routines. That provides a 3.5% gain. Better profiling may help
by compiling more methods. I haven't looked at the profiler since the
last optimisation.  So would a little tuning, 1% of the time (out of
5% in compiled code) is spent building the new context during a
message send, most of that time could be saved.  It is however
producing a performance gain. Which is enough to make bug fixing the
priority again.

The list of things to do before a 1.0 is here:

 http://minnow.cc.gatech.edu/squeak/5793

Nothing on it is hard or risks destabilising things.

Bryce

On 6-Oct-06, at 4:25 PM, <[hidden email]> wrote:

Actually I don't think JIT is a sensible description at all; it isn't  
accurate and it doesn't really indicate the advantages that Exupery  
could have. For example, no extra startup costs, easier extension/
maintenance/optimising because it is written in a sensible language,  
access to all of the reflexive capabilities of the system, trivial  
fallback  if the system is run on an unsupported platform  (it just  
doesn't do the compiles and leaves everything to the interpreter),  
potential for using a spoon-like inter-image communication system to  
allow the compiles to run in a different image/machine, and... well I  
could probably go on.

JIT really has been tied to a very limited concept of "oh I need  
this, let's compile something, er, now where was I?" approach. The  
compiler has to be internal to the VM and so far as I'm aware is  
pretty much tied to C/C++ or worse.

Exupery is CALIL - Compile At Leisure, Install Later. Oh, and you  
could even  have setup where an external compiler-server caches a lot  
of methods and avoids even doing the compile a lot of the time.


tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
User: A harmless drudge.

From: Jecel Assumpcao Jr
>Sent: Monday, September 18, 2006 2:10 PM
>
>A more radical change to the Squeak VM was Anthony Hannan's VI4 work,
>which gave us better performance and real closures. But though his new
>bytecodes were cleaner, my impression is that he felt the gain wasn't
>enough to justify losing the historical connection to the "blue book"
>design.

So what happened with this?  I have seen several references in this list
(this is the first one I found) of someone making a good closure
implimentation and it getting rejected.  Why are they getting rejected?  I
think real completel closures are a requirement for any modern language.  
Even Java and C++ (!!!) will have then within a few years.