Bluish Coder

Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.


2014-12-22

Self Benchmarking

I was asked on twitter about the current speed of the Self implementation. The request was for a method send benchmark so I wrote a simple one and compared against Pharo, a Smalltalk implementation.

The implementation and technology behind Self is quite old in comparison to modern compiler implementations but at the time it was state of the art. I hoped it would hold up reasonably well. The test I wrote in Self was:

(|
  doSomething = ( ^self ).
  test = ( |n <- 0|
           [ n < 100000000 ] whileTrue: [ doSomething. n: n + 1 ]
         )
|)

Running this in the Self shell shows:

"Self 1" _AddSlots: ...code snippet from above...
shell
"Self 2" [ test ] time.
2587

2.5 seconds seems a bit slow to me but I tested in Pharo to confirm and to see how it compares. The Pharo code looks almost exactly like the Self code:

doSomething = ^self
test = |count|
       count := 0.
       [ count < 100000000 ] whileTrue: [
         count := count + 1.
         doSomething.
       ].

[ MyObject new test ] timeToRun
  => 0:00:00:00.239

That’s 239ms vs 2,587ms, a factor of over 10x. Further investigation revealed that calling ‘time’ in Self seems to cause the code to run slower. If I call the ‘test’ method first, and then call ‘time’ then it’s much faster:

"Self 2" [ test ] time.
2587
"Self 3" [ test ] time.
2579
"Self 4" test.
nil
"Self 5" [ test ] time.
650
"Self 6" [ test ] time.
628

At 650ms it is about 2.7x slower than Pharo, an improvement over 10x. More investigation is needed to see if there is room for other improvements.

The Self implementation has some primitives that can be changed to show debugging information from the JIT. All primitives can be listed with:

primitives primitiveList do: [ | :e | e printLine ].

Looking through this shows some interesting ones prefixed with _Print that can be set to output debug data. One is _PrintCompiledCode. Setting this to true allows viewing the generated assembler code on the Self console.

"Self 16" _PrintCompiledCode: true.
false
"Self 17" 40 + 2.
...
  // loadOop2
movl $0xa0 (40), #-16(%ebp)
  // loadOop2
movl $0x8 (2), #-20(%ebp)
  // loadArg
movl #-20(%ebp), %ebx
movl %ebx, #4(%esp)
  // selfCall
movl #-16(%ebp), %ebx
movl %ebx, (%esp)
nop
nop
nop
call 0x8186597 <SendMessage_stub> (bp)
  // begin SendDesc
jmp L7f
  .data 3
jmp L9f
  .data 0
  .data 0
  .data 0x4578341 ('+')
  .data 4
L7: 
L8: 
  // end SendDesc
movl %eax, #-16(%ebp)
  // epilogue
movl #-16(%ebp), %eax
  // restore_frame_and_return
leave
ret

Others, like _PrintInlining display debug information related to inlining code.

"Self 18" _PrintInlining: true
fales
"Self 19" test.
*inlining size, cost 0/size 0 (0x8b7e864)
*PIC-type-predicting - (1 maps)
*type-casing -
*inlining - (smallInt.self:153), cost 1/size 0 (0x8b7ee38)*
 *inlining asSmallInteger (number.self:108), cost 1/size 0 (0x8b7fa94)*
  *inlining raiseError, cost 0/size 0 (0x8b80530)*
  *inlining asSmallIntegerIfFail: (smallInt.self:302), cost 0/size 0 (0x8b808fc)*
 *inlining TSubCC:
 *cannot inline value:With:, cost = 10 (rejected)
 *marking value:With: send ReceiverStatic
 *sending value:With:
*sending -
*inlining size:, cost 0/size 0 (0x8b8434c)
*inlining rep, cost 0/size 0 (0x8b846a8)
*PIC-type-predicting removeFirstLink (1 maps)
*type-casing removeFirstLink
*inlining removeFirstLink (list.self:300), cost 2/size 0 (0x8b84b48)*
 *inlining next, cost 0/size 0 (0x8b85628)
 *PIC-type-predicting remove (1 maps)
 *type-casing remove
 *cannot inline remove, cost = 9 (rejected)
 *sending remove
*sending removeFirstLink
*PIC-type-predicting value (1 maps)
*type-casing value
*inlining value, cost 0/size 0 (0x8b86570)*
*sending value
*inlining asSmallInteger (number.self:108), cost 1/size 0 (0x8b7e5b0)*
 *inlining raiseError, cost 0/size 0 (0x8b7f074)*
 *inlining asSmallIntegerIfFail: (smallInt.self:302), cost 0/size 0 (0x8b7f440)*
*inlining TSubCC:
*cannot inline value:With:, cost = 10 (rejected)
*marking value:With: send ReceiverStatic
*sending value:With:
nil

For more involved benchmarks there is some code shipped with the Self source. It can be loaded with:

"Self 28" bootstrap read: 'allTests' From: 'tests'.
reading ./tests/allTests.self...
reading ./tests/tests.self...
reading ./tests/programmingTests.self...
reading ./tests/debugTests.self...
reading ./tests/lowLevelTests.self...
reading ./tests/numberTests.self...
reading ./tests/deltablue.self...
reading ./tests/sicTests.self...
reading ./tests/branchTests.self...
reading ./tests/nicTests.self...
reading ./tests/testSuite.self...
reading ./tests/languageTests.self...
reading ./tests/cons.self...
reading ./tests/benchmarks.self...
reading ./tests/richards.self...
reading ./tests/parser.self...
reading ./tests/parseNodes.self...
modules allTests

There are methods on the bootstrap object for running the tests and printing results. For example:

"Self 32" benchmarks measurePerformance

                 compile    mean       C    mean/C       %
recur:                 5       0
sumTo:                 2       7
sumFromTo:             2       7
fastSumTo:             2       6
nestedLoop:            2      10
...

There is also measurePerformance2 and measurePerformance3 methods. The code comments for the measure2 and measure3 methods explain the differences.

Self 2 was well known for generating very fast code that compared favourably with C. This implementation of this was described in Craig Chamber’s thesis. Compilation was slow however so in Self 3 and 4 two new compilers were created. These were ‘nic’ and ‘sic’. I believe this is covered in Urs Hölzle’s thesis The ‘nic’ compiler is the ‘Non Inlining Compiler’ and is simpler to implement. It’s the compiler you write to get Self bootstrapped and running on new platforms fairly quickly. There is no inlining and no type feedback so performance is slower as shown by the benchmarking when changing the compiler used, as described below. The ‘sic’, or ‘Single Inlining Compiler’, generates better code through more optimisations. While neither is as fast as the Self 2 compiler it is faster to compile code and makes for a better interactive system. You can read more about this in the Merlintec Self FAQ.

There is a defaultCompiler slot in the benchmark object that can be set to nic or sic to compare the different JIT compilers that Self implements. Comparing the ‘nic’ compiler vs the ‘sic’ compiler shows a speedup of about 6x in the ‘richards’ benchmark when using ‘sic’.

There’s probably a fair bit of low hanging fruit to improve run times. I don’t think the x86 backend has had as much work on it as the Sparc or PPC backends. The downside is much of the compiler code is written in C++ so for people interested in ‘Self the language’ it’s not as fun to hack on. Klein was an attempt to write a Self VM in Self and includes a compiler and assembler which might make a more interesting project for those that want to use Self itself to implement compiler code.

Tags: self 

2014-12-18

Using Freenet

I’ve been following the Freenet project for many years, occasionally firing it up and seeing if I can do anything useful with it. I’ve been using it regularly over the last month and it has come a long way since I first tried it. It’s much faster than what it was in the past. This post describes a bit of how I use it and some of the issues I worked around when publishing content.

Overview

There are no dynamic servers on Freenet. No user hosts a site. It’s a data store and users push the data into the content store which then becomes retrievable by anyone with the key. Freenet is essentially a large encrypted distributed hash table.

Nodes set aside an amount of disk space and users choose to store data under a key. Retrieval of the key goes out into the distributed hash table and returns the data associated with it. Inserting data into the store pushes that data out into other nodes and is not generally stored in your own node. Requesting data sends the request over the network and the data migrates to your node to return the data. A scheme is used to enable recovery from data loss. M of N segments of your data can be lost but the full data can still be recovered. The network is lossy in that as more data is inserted, less frequently requested data drops out. Data stored is immutable. Once it is in the store with a key it will always be associated with that data.

Freenet data is requested using keys. There are different types of keys. A high level overview would be:

KSK@somewhere
A KSK key can be chosen by the inserter. The 'somewhere' portion of the key can be any value. This allows generating keys to access data using easier to remember words or phrases. The downside is they can be re-inserted by anyone with different data. What you get when you request the key depends on what data has been inserted by different users under it.
CHK@...
CHK keys have the `...` portion computed based on the hash of the data content. These have the advantage that the key is always the same for the same data. If data for a CHK key has dropped out of the network anyone can 'heal' that data by reinserting the same file. The hash for the CHK key will be the same and the data will become available again under that same key. This is like being able to have any user fix a 404 response on the standard internet by reuploading the same file anywhere.
SSK@...
An SSK key has a unique cryptographically generated hash that is different for any given insert of data. These cannot be 'healed' if the data drops out as a re-insert will have a different key.
USK@.../foo/1
A USK key allows updateable content. Note the number at the end. This increments everytime new data for the key is inserted. When requesting data freenet can look for the highest number available and return that. It's useful for freenet hosted blogs which have reguarly updated content.

Setup

The freenet software really needs to run 24x7 to be effective. I followed the headless install instructions to install on a server machine and access the freenet proxy on my client machines using an SSH tunnel. An SSH commmand like the following sets up local ports that tunnel to the server so they can be accessed locally:

ssh -L 8888:127.0.0.1:8888 -L 8080:127.0.0.1:8080 -L 9481:127.0.0.1:9481 me@myserver.local

The 8888 port is for the freenet proxy software where you access most freenet functionality from the browser. Port 8080 is for the Freenet Message System if you install that and 9481 is for the API interface that jSite uses.

It takes a few hours for a new freenet node to establish itself and get up to speed. Expect much slowness initially. It gets better though.

Social Networking on Freenet

Freenet has some social networking functionality. There is a web of trust for identities, distributed anonymous email, twitter-like microblogging, forums and IRC like chat. How to set these up is described in the Freenet Social Networking Guide. Setting up an identity in the web of trust and Sone for the microblogging will give a good start to using freenet socially.

You can create as many web of trust identities as you want and switch between them for different purposes. I use Freenet non-anonmously and my identity on there is associated with my real world identity but I could also have anonymous ones for other purposes.

Freenet Sites

A freenet site is usually stored under a USK key so it can be updated. Software to insert a directory of HTML as a USK is the easiest way of uploading a site or blog. I use jSite. I mirror this blog to freenet under the key USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-7. Note the negative number at the end. When requested this results in freenet starting from edition ‘7’ and looking for the most recent published edition from there. Sites can be bookmarked in the freenet proxy and it will automatically look for and update the bookmark when a new edition is inserted.

There were some issues I had to workaround when mirroring my Jekyll based blog. I have absolute links in the blog that references other pages. These don’t work if copied directly to a freenet site as the freenet proxy has the content key as the initial part of the URL. So a link to a page in the proxy looks like /USK@longhash/bluishcoder/7/2014/12/17/changing-attributes-in-self-objects.html. An internal link that starts with / to go to a page will not work as it doesn’t contain the USK key prefix. I tried modifying Jekyll to use relative URLs but wasn’t successful. The approach I ended up taking was to follow the advice in this github issue. My _config.yml file contains these baseurl entries:

baseurl: "file:///some/path/bluishcoder/_site"
#baseurl: /USK@longlonghash/bluishcoder/7
#baseurl: "http://bluishcoder.co.nz"

All my internal links in blog posts have the baseurl prefixed. For example (Remove the backslash - I had to add it to prevent Jekyll from replacing it with the baseurl here):

[link to a video]({\{site.baseurl}}/self/self_comment.webm)

This gets replaced at blog generation time by the baseurl entry in _config.yml. I generate my internet based blog with the relevant baseurl, copy that to my webserver, then generate the freenet based one with the correct baseurl and push that to freenet using jSite. This is a bit tedious but works well. A blog system that uses only relative URLs would be a lot easier as you can just insert the site directly.

Note that freenet sites cannot use JavaScript and some content is filtered out for security reasons. Simple HTML and CSS works best.

Photo heavy sites

I have a site heavy in photos which is a mirror of some photos from my Pitcairn Island trip. This is under key USK@2LK9z-pdZ9kWQfw~GfF-CXKC7yWQxeKvNf9kAXOumU4,1eA8o~L~-mIo9Hk7ZK9B53UKY5Vuki6p4I4lqMQPxyw,AQACAAE/pitcairnisland/3. The interesting problem with photo heavy sites is how best to present the photos while also preventing them from dropping out of the network.

If the main page of the site has thumbnail images and allows the user to see the full image by selecting the thumbnail then the thumbnails tend to stay alive as they are most requested. Unfortunately some of the full images will tend to drop out eventually. A recommended approach by long time freenet users is to link to the full photo in the IMG tag but scale it to thumbnail size. This causes the page to have all the full size images scaled and is slow to load. But all the images stay alive.

I like the fast loading approach of thumbnails though so tried to find a middle ground. Image preloading using CSS seemed like a viable solution but Freenet’s content filter has issues with it. With some tweaking of that this approach would work well. The thumbnails would load for quick viewing and the full images would pre-load without the user noticing that the page is still loading. This should result in most images staying around.

The approach I ended up using was to have a hidden DIV at the end of the page with the full sized images. They don’t display and cause the full size images to be retrieved while the user sits on the main page. The downside is the page still shows that it’s loading which isn’t optimal. I also link to a page that has the full sized images scaled to thumbnail size as a viewing option. Hopefully the issue with the CSS preloading approach can be resolved as that has a better user experience.

Conclusion

Other than mirring my blog and using Sone I haven’t done too much else. There is a ‘bitcoin over freenet’ program that mirrors the blockchain in freenet and allows submitting and retrieving transactions that looks interesting to explore. Freenet would seem to be useful for some things Tor is used for (dissemination of information under oppressive regimes) without the requirement of needing an active server that can be located and attacked.

There’s a great set of PDF slides that cover more about what Freenet can do if you’re interested in looking into it more.

My interest has been more about looking at how freenet can be used as a more encrypted and non-hosted distributed alternative to services like Twitter, Facebook, hosted email and the like. As long as you can put up with higher latency and the different idioms an ‘immutable internet that decays’ requires it seems that this is viable.

I’m curious what other services people could build on top of it.

Tags: freenet 

2014-12-17

Changing Attributes in Self objects

A question came up in the Self irc channel today about how to change the ‘comment’ string for an object. Comments are stored as attributes on an object. These are accessed using mirrors.

A mirror for an object can be obtained using the asMirror method. The trait traits mirrors abstractMirror provides a number of methods that can be used to change the object via the mirror. This involves everything that is normally done through the programming environment. It includes adding, removing and changing slots, categories, attributes amongst other things. By drilling down in this trait you can see a programming category, which expands to include a changing annotation category and that holds a comments category. Within that you can find the methods for setting comments.

The video below shows the steps to find this from within the programming environment and demonstrates changing the comment on the initial shell object on the desktop. The code to change that comment is just:

self asMirror comment: 'hello world'

Tags: self 

2014-11-12

Revisiting Alice ML

Alice ML is a functional programming language base on Standard ML with extensions to support concurrent and distributed programming. I first got interested in it back in 2004 when version 1.0 was released and used it on and off for a couple of years until development stalled. It’s hard to believe that ten years has passed since that post!

A few years ago Gareth Smith fixed some bitrot in the CVS repository and fixed a number of bugs and adding new features. These were placed in a bitbucket repository but development stalled again.

I recently started tinkering with the language again, building some old projects I had written using it. I fixed some minor bitrot from Gareth’s work and a couple of bugs and put the results, with the permission of Gareth and the original Alice ML developers, in an aliceml github repository. Instructions for building on Linux and Mac OS X are in the README.

For a taste of what’s interesting about Alice ML I recommend the Short Tour of Alice. Features include:

  • Futures: laziness and light-weight concurrency with implicit data-flow synchronisation
  • Higher-order modules: higher-order functors and abstract signatures
  • Packages: integrating static with dynamic typing and first class modules
  • Pickling: higher-order type-safe, generic & platform-independent persistence
  • Components: platform-independence and type-safe dynamic import & export of modules
  • Distribution: type-safe cross-platform remote functions and network mobility
  • Constraints: solving combinatorical problems using constraint propagation and programmable search

The collection of Alice ML Papers is a good read. The features that most attracted me to Alice ML at the time were lightweight threads using futures and promises for dataflow combined with the ability to do typesafe distribution and runtime loading of modules.

I put some of the known issues in the github issue tracker and I encourage anyone finding problems to add them. I created a subreddit with a few links - mostly as a land claim so that the subreddit doesn’t get squatted - but it might be useful to collect or discuss papers and documentation. There’s a #aliceml channel on Freenode as well.

Why do this? I still like to use Alice ML and explore some of the ideas in it. I’m sure there are other interested people out there. I hope to at least help keep the bitrot away in the existing code as it would be a shame for Alice ML to disappear.

Tags: aliceml 

2014-10-22

Installing NixOS on Linode with Encrypted Partitions

A while back I updated the instructions to install NixOS on Linode on the NixOS Wiki. This post adds to this to include encrypted partitions. It’s based on those wiki instructions and my previous post on installing NixOS to an encrypted drive.

Some points to keep in mind when running a Linode with an encrypted drive are:

  • When you reboot you will need to access the Linode console to enter the password to mount the encrypted partition.
  • Because the server is located remotely it’s possible for Linode or a party in a similar position to trap the console input to capture your password. So while encryption prevents a malicious admin from scanning your disks it won’t prevent someone located at Linode from rebooting and capturing the password you enter.
  • I’m sure there are other weaknesses such as keys existing in memory while the Linode is running. Make sure you are ok with the attack points in this setup.

Boot a Linode into Rescue Mode

First step is to create the Linode as usual. I tested with a $20/month Linode 2048. Create two disk images. They should be:

  • A boot disk that will be unencrypted. I made this 1GB which is way oversized for what it needs to be but makes math easy.
  • A root disk that will be encrypted. I made this the remainder of my free disk space.

From the Linode manager choose the option to boot into the new Linode in Rescue mode. Make sure the disks are setup as:

  • /dev/xvda is the boot disk.
  • /dev/xvdb is the root disk.

When the recovery image is booted you can ssh into it with the instructions in the Remote Access tab of the Linode manager under Console Access. This will get you to a root prompt on the Linode to perform the rest of the steps.

Encryption Setup

Perform the following commands to setup the disk encryption:

# cryptsetup luksFormat /dev/xvdb
# cryptsetup luksOpen /dev/xvdb enc-pv
# pvcreate /dev/mapper/enc-pv
# vgcreate vg /dev/mapper/enc-pv
# lvcreate -L 1G -n swap vg
# lvcreate -l 11525 -n root vg

Note that these operate on the /dev/xvdb disk which is the root disk we created earlier. You will be prompted for a passphrase during the luksFormat and luksOpen commands. Make sure you remember this as this is the passphrase needed when rebooting.

The lvcreate lines create the partitions for swap and root partition. The 1G means a one gigabyte swap file. The 11525 is the extent for the remainder of the disk space. I found this number by initally running lvcreate -L 99G -n root vg which is bigger than the 40GB available on the linode. This gave an error message showing the maximum extent to use which was 11525 for me.

Formatting and Mounting

Format the new partitions with:

# mkfs.ext4 -L boot /dev/xvda
# mkfs.ext4 -O dir_index -j -L root /dev/vg/root
# mkswap -L swap /dev/vg/swap
# swapon /dev/vg/swap

To install NixOS we need to mount the partitions under /mnt:

# mount /dev/vg/root /mnt
# mkdir /mnt/boot
# mount /dev/xvda /mnt/boot

Installing NixOS

The installation is relatively simple. First install the Nix package manager:

# bash <(curl https://nixos.org/nix/install)
# . /root/.nix-profile/etc/profile.d/nix.sh

Set the channel to be NixOS:

# nix-channel --remove nixpkgs
# nix-channel --add http://nixos.org/channels/nixos-14.04 nixos
# nix-channel --update

Create a default configuration file for some NixOS packages we will need for the install later:

# cat <<EOF > configuration.nix
  { fileSystems."/" = {};
    boot.loader.grub.enable = false;
  }
  EOF

Install the NixOS installation software:

# export NIX_PATH=nixpkgs=/root/.nix-defexpr/channels/nixos:nixos=/root/.nix-defexpr/channels/nixos/nixos
# export NIXOS_CONFIG=/root/configuration.nix
# nix-env -i -A config.system.build.nixos-install \
             -A config.system.build.nixos-option \
             -A config.system.build.nixos-generate-config \
             -f "<nixos>"

Generate a default configuration file for the bootable system:

# nixos-generate-config --root /mnt

This creates a /mnt/etc/nixos/configuration.nix file which should be edited to install the software you want. It also requires some changes for Grub and the disk encryption. Replace the existing section related to Grub 2 in this file with:

# Use the GRUB 1 boot loader.
boot.loader.grub = {
 enable = true;
 version = 1;
 extraPerEntryConfig = "root (hd0)";
 device = "nodev";
};

For the encryption support add:

boot.initrd.luks.devices = [
  { name = "root"; device = "/dev/xvdb"; preLVM = true; }
];

To enable OpenSSH access to the Linode add:

services.openssh.enable = true;

Now run the install:

# nixos-install

This will take some time to download and install things.

Post install

Once nixos-install completes the following commands will need to be run to fixup Grub 1 usage on Linode. This must be done before rebooting:

# mkdir -p /mnt/boot/boot/grub
# cd /mnt/boot/boot/grub
# ln -sv ../../grub/menu.lst /mnt/boot/boot/grub

First boot

Create a new Configuration Profile in the Linode Manager for the Linode. Set the kernel to pv-grub-x86_64. Set the disks as they were setup in the Rescue boot. Everything else can be left at the default.

Boot the new Configuration. Now you will need to ssh back into the Linode console so you can enter your passphrase. This will continue the booting process. Login as root. There is no initial password. Set one:

# passwd

By default you won’t be able to ssh as root so you should set up a normal user:

# useadd -m myuser
# passwd myuser
# usermod -a -G wheel myuser

The latter command lets you use sudo as that user. You should now be able to ssh into the Linode with the newly created user.

Customization

These steps install the stable version of NixOS. This does not receive new packages, only updates to existing ones. I like to live on the bleeding edge so I use nixos-unstable. You can switch to this by running the following as root:

# nix-channel --add http://nixos.org/channels/nixos-unstable nixos
# nixos-rebuild switch --upgrade

If you prefer vim to nano as an editor, add the following to /etc/nixos/configuration.nix:

environment.systemPackages = with pkgs; [
  vim
];

environment.variables.EDITOR = pkgs.lib.mkOverride 0 "vim";

If you need non-free packages, add:

nixpkgs.config.allowUnfree = true;
Tags: nixos 


This site is accessable over tor as hidden service mh7mkfvezts5j6yu.onion, or Freenet using key:
USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-7/


Tags

Archives
Links