Netduino home hardware projects downloads community

Jump to content


The Netduino forums have been replaced by new forums at community.wildernesslabs.co. This site has been preserved for archival purposes only and the ability to make new accounts or posts has been turned off.
Photo

SimpleNGen 1.4


  • Please log in to reply
31 replies to this topic

#1 Corey Kosak

Corey Kosak

    Advanced Member

  • Members
  • PipPipPip
  • 276 posts
  • LocationHoboken, NJ

Posted 06 July 2011 - 09:29 PM

I've pushed this project a little further along and now it has support for compiling multiple methods. Currently the rules are:

  • There is one designated 'primary' method, with a standard signature, suitable for calling from C#
  • There can be additional other methods, with whatever signature you like
  • These methods can all each other, or recursively call themselves

The system still has some limitations (and, no doubt, bugs) but is currently working well enough to for me to write Quicksort and compare its interpreted vs. compiled performance. I chose Quicksort because it's sort of cool and also because its implementation involves both recursion and a couple of subroutines. The code is below. As with all the previous versions of SimpleNGen, I work with pointer types rather than arrays, because it's easier to for me compile code that uses pointer semantics. Although this means I am using unsafe code, and unsafe code is evidently not fully supported on the Micro Framework, it appears to work well enough for my purposes.

My test program actually compares three different cases:
  • Interpreted unsafe code (using pointers)
  • Interpreted safe code (using arrays)
  • Compiled code (using pointers)
#1 and #3 are using exactly the same source code, which is pretty cool.

Below are the results for an array of 10,000 ints. The compiled code is apparently about 200X faster. One surprise was that the interpreted code using arrays was quite a bit faster than the interpreted-but-unsafe code using pointers. I don't know why that should be so (of course the compiled version blew them both away).

Interpreted (pointer version): 00:00:22.5213866
Interpreted (array version): 00:00:17.6493440
Compiled: 00:00:00.0873174

The following code fragments are:
  • The Quicksort code with unsafe pointers (for tests 1 and 3)
  • The safe version with arrays (test 2)
  • The driver
Also attached is a zip file with the test program and the SimpleNgen 1.4 compiler.

The unsafe version with pointers, suitable for interpretation or compilation:
  /// <summary>
  /// From the Wikipedia entry for Quicksort
  /// </summary>
  public unsafe static class Quicksort {
    public static void Doit(int left, int right, int dummy0, int dummy1, int* array) {

      if(right>left) {
        var pivotIndex=(left+right)>>1;
        var pivotNewIndex=Partition(array, left, right, pivotIndex);
        Doit(left, pivotNewIndex-1, 0, 0, array);
        Doit(pivotNewIndex+1, right, 0, 0, array);
      }
    }

    private static int Partition(int* array, int left, int right, int pivotIndex) {
      var pivotValue=array[pivotIndex];
      Swap(array+pivotIndex, array+right);
      var storeIndex=left;
      for(var i=left; i<right; ++i) {
        if(array[i]<pivotValue) {
          Swap(array+i, array+storeIndex);
          ++storeIndex;
        }
      }
      Swap(array+storeIndex, array+right);
      return storeIndex;
    }

    private static void Swap(int *a, int *b ) {
      var temp=*a;
      *a=*b;
      *b=temp;
    }
  }

The array version, for comparison's sake:
  public static class Quicksort_Array {
    public static void Doit(int left, int right, int[] array) {

      if(right>left) {
        var pivotIndex=(left+right)>>1;
        var pivotNewIndex=Partition(array, left, right, pivotIndex);
        Doit(left, pivotNewIndex-1, array);
        Doit(pivotNewIndex+1, right, array);
      }
    }

    private static int Partition(int[] array, int left, int right, int pivotIndex) {
      var pivotValue=array[pivotIndex];
      Swap(ref array[pivotIndex], ref array[right]);
      var storeIndex=left;
      for(var i=left; i<right; ++i) {
        if(array[i]<pivotValue) {
          Swap(ref array[i], ref array[storeIndex]);
          ++storeIndex;
        }
      }
      Swap(ref array[storeIndex], ref array[right]);
      return storeIndex;
    }

    private static void Swap(ref int a, ref int b ) {
      var temp=a;
      a=b;
      b=temp;
    }
  }
}

The driver
using Kosak.SimpleInterop;
using System;
using Microsoft.SPOT;
using Microsoft.SPOT.Hardware;

namespace NgenSandbox {
  public class Program {
    public static void Main() {
      const int numItems=10000;
      const int randomSeed=12345;
      var interpretedTime_InterpretedPointer=new QuicksortTester(numItems, randomSeed).RunInterpreted_Pointer();
      var interpretedTime_InterpretedArray=new QuicksortTester(numItems, randomSeed).RunInterpreted_Array();
      var compiledTime=new QuicksortTester(numItems, randomSeed).RunCompiled();

      Debug.Print("Elapsed times for "+numItems+" items (random seed is "+randomSeed+")");
      Debug.Print("Interpreted (pointer version): "+interpretedTime_InterpretedPointer);
      Debug.Print("Interpreted (array version): "+interpretedTime_InterpretedArray);
      Debug.Print("Compiled: "+compiledTime);
    }
  }

  public class QuicksortTester {
    private readonly int[] data;

    public QuicksortTester(int count, int seed) {
      Debug.Print("Initializing data");
      var r=new Random(seed);
      this.data=new int[count];
      for(var i=0; i<data.Length; ++i) {
        data[i]=r.Next();
      }
    }

    public unsafe TimeSpan RunInterpreted_Pointer() {
      DumpData("Interpreted_Pointer: before");
      var start=Utility.GetMachineTime();
      fixed(int* datap=data) {
        Quicksort.Doit(0, data.Length-1, 0, 0, datap);
      }
      var end=Utility.GetMachineTime();
      DumpData("Interpreted_Pointer: after");
      return end-start;
    }

    public TimeSpan RunInterpreted_Array() {
      DumpData("Interpreted_Array: before");
      var start=Utility.GetMachineTime();
      Quicksort_Array.Doit(0, data.Length-1, data);
      var end=Utility.GetMachineTime();
      DumpData("Interpreted_Array: after");
      return end-start;
    }

    public TimeSpan RunCompiled() {
      DumpData("Compiled: before");
      var start=Utility.GetMachineTime();
      NativeInterface.Execute(QuicksortOutput.opCodes, 0, data.Length-1, 0, 0, data, null, null, null);
      var end=Utility.GetMachineTime();
      DumpData("Compiled: after");
      return end-start;
    }

    private void DumpData(string title) {
      Debug.Print("*** "+title+" ***");
      for(var i=0; i<data.Length; ++i) {
        Debug.Print(i+" "+data[i]);
      }
    }
  }
}

Attached Files


  • Chris Walker likes this

#2 Chris Walker

Chris Walker

    Secret Labs Staff

  • Moderators
  • 7767 posts
  • LocationNew York, NY

Posted 06 July 2011 - 09:55 PM

Very awesome, Corey. Thanks for continuing to improve SimpleNGen! Is it okay with you if we build a version of 4.2 (when the RTM ships) with this built in? Chris

#3 Corey Kosak

Corey Kosak

    Advanced Member

  • Members
  • PipPipPip
  • 276 posts
  • LocationHoboken, NJ

Posted 06 July 2011 - 10:00 PM

Is it okay with you if we build a version of 4.2 (when the RTM ships) with this built in?


Definitely!

#4 Chris Walker

Chris Walker

    Secret Labs Staff

  • Moderators
  • 7767 posts
  • LocationNew York, NY

Posted 06 July 2011 - 10:08 PM

Definitely!

Thank you! We may have to create a new user class of "Netduino Wizard" ;)

#5 Corey Kosak

Corey Kosak

    Advanced Member

  • Members
  • PipPipPip
  • 276 posts
  • LocationHoboken, NJ

Posted 06 July 2011 - 10:47 PM

Thank you! We may have to create a new user class of "Netduino Wizard" ;)


Thanks! Maybe you can start by raising my file attachment quota on this forum, as I'm almost out of space.

Also, one thing that would really be useful is the following. I've wanted to write interrupt-handling style support for SimpleNgen (e.g. periodically polling a pin and/or getting an interrupt on a signal edge). The problem is I don't know my way around the firmware very well, and figuring it out may take me a lot of time.

If someone out there were able to provide C++ code that does those things (written in the style as modifications to the firmware), then I could crib from that code and figure out what needs to be done for SimpleNgen. For example, I got a huge amount of mileage from the post Chris made here regarding direct access to the I/O ports.

#6 Chris Walker

Chris Walker

    Secret Labs Staff

  • Moderators
  • 7767 posts
  • LocationNew York, NY

Posted 06 July 2011 - 11:36 PM

Thanks! Maybe you can start by raising my file attachment quota on this forum, as I'm almost out of space.

Done :)

#7 rhind

rhind

    New Member

  • Members
  • Pip
  • 3 posts

Posted 07 July 2011 - 05:54 AM

Interpreted unsafe code (using pointers)

  • Interpreted safe code (using arrays)
  • Compiled code (using pointers)
#1 and #3 are using exactly the same source code, which is pretty cool.


Out of interest, do you think would it be possible for a future version of SimpleNGen to replace arrays with pointers and pointer arithmetic? You wouldn't benefit from pointer++ operations, but array access would then come down to pointer + i which could be handled by SimpleNGen if I understand how it works.

This would given a large speed boost to 'safe' code that uses arrays rather than having to write unsafe code. This would allow you to test the safe code in debug mode but have it ngened in release mode for performance?

Thanks

Russell

#8 Corey Kosak

Corey Kosak

    Advanced Member

  • Members
  • PipPipPip
  • 276 posts
  • LocationHoboken, NJ

Posted 07 July 2011 - 03:23 PM

Out of interest, do you think would it be possible for a future version of SimpleNGen to replace arrays with pointers and pointer arithmetic?

I think I would disagree with such an approach for a couple of reasons. The goal of this project (and the Fluent Interop project which preceded it) is to provide a means of writing native code that is less painful than the original solution (which involves integrating C++ code into the firmware and then reflashing the Netduino). The underlying assumption behind the project is that people will continue to use (interpreted) C# for most of their program, but might rewrite a few performance-critical routines (such as I/O operations) in native code.

The various ways one might provide that native code are:
  • Integrating C++ into the firmware and re-flashing
  • Writing the code in C or C++ and using gcc as a cross compiler, then pushing bytes from the compiler output (using a tool that has not yet been written) to the Netduino
  • Using a subset of C# and running SimpleNGen

I happen to find #3 to be an especially pleasant way of writing native code. But one should never lose sight of the fact that one is writing native code. People should not assume that SimpleNgen ever intends to provide full native compiler of arbitrary C# code. In particular, it will never support any managed features at all. (Other people on this forum have expressed a desire to write a full native compiler (along with, evidently, corresponding runtime support), and I hope they are successful).

An array type like int[] comes with a lot of baggage from the managed side that I don't intend to support, such as .GetHashCode() and .Clone() and .GetType() and even .Length. Furthermore array types come with the assumption that they will be treated like a .NET reference (e.g. if you were to stash one in a static variable, the garbage collector would not collect the object). On the other hand, the C# type "pointer" has basically the semantics I want, namely a memory address of a byte or int. Finally pointer types have the behavior you typically want for native code, namely the ability to efficiently step through a block of memory, without bounds checks or other drama.

#9 EdwardS.

EdwardS.

    Member

  • Members
  • PipPip
  • 14 posts

Posted 09 July 2011 - 08:11 PM

Thank you! We may have to create a new user class of "Netduino Wizard" ;)



Chris, do you think MS will pick this up ?

#10 Klop

Klop

    Advanced Member

  • Members
  • PipPipPip
  • 49 posts

Posted 13 July 2011 - 09:48 AM

Hi, Is it possible for anyone to do a Netduino Plus firmware build with the SimpleNGen? I need access to the SD card. Thanks.

#11 Mario Vernari

Mario Vernari

    Advanced Member

  • Members
  • PipPipPip
  • 1768 posts
  • LocationVenezia, Italia

Posted 13 July 2011 - 12:01 PM

Hello Klop. I think the only guy could build the N+ firmware is Chris Walker. I've tried time ago to set up the firmware for my Plus, but it's totally out of range for the free GCC compiler. Even cutting off almost any feature, the overflow is behind the door. As far I know the only way to fit all the stuffs contained in the N+ is compile the sources using the RVDS. The problem is that really expensive... I expressed many times my dislike upon this argument. However, it seems there's no workaround at the moment. Cheers
Biggest fault of Netduino? It runs by electricity.

#12 Chris Walker

Chris Walker

    Secret Labs Staff

  • Moderators
  • 7767 posts
  • LocationNew York, NY

Posted 13 July 2011 - 03:10 PM

vote for it hereEdwardS.: I think it would be great for Microsoft to include a standardized runtime interop feature in .NET MF. Please vote for it here.

Klop: we'll build a version of the final .NET MF 4.2 with Corey's latest-and-greatest SimpleNGEN...for all three Netduinos.

Mario: I've heard rumors that the newest GCC compilers create much smaller code. A few community members have been hacking away at getting the .NET MF build scripts working with the latest versions of the compiler. Does that help?

Chris

#13 Klop

Klop

    Advanced Member

  • Members
  • PipPipPip
  • 49 posts

Posted 14 July 2011 - 09:48 AM

Klop: we'll build a version of the final .NET MF 4.2 with Corey's latest-and-greatest SimpleNGEN...for all three Netduinos.

Hi Chris,

Do you have an estimate on the final .NET MF 4.2 build for all three Netduinos?

Thanks.

#14 Klop

Klop

    Advanced Member

  • Members
  • PipPipPip
  • 49 posts

Posted 04 August 2011 - 04:19 PM

Hi Chris, Now back home from vacation :) Do you have an estimate on the final .NET MF 4.2 build for all three Netduinos with Corey's latest-and-greatest SimpleNGEN?

#15 JasonS

JasonS

    New Member

  • Members
  • Pip
  • 3 posts

Posted 06 August 2011 - 08:40 PM

I have just gotten into NetDuino, and was looking for some way to do atleast a small amount of high speed work in a larger project (specifically, I need high speed for sending IR signals for controlling various consumer electronics). This project looks terrific, and almost exactly what I need (great job Corey!). In reading through this, it appears that I need to wait for the 4.2 build with the appropriate items included, so I am also curious as to the timing on this. One thing that I need to do, which I have not yet seen an example of, or a method for in browsing through the SimpleNGen compiler code, is access to time/timers/sleeps/etc. The protocols I am interested in are time based, with no shared clock - so for example I need to trigger a 38kHZ carrier signal (generated by a PWM) for ~600 microseconds. If the code is fast enough, I can generate the 38kHZ carrier without the PWM which would allow me to use only one pin, but either way I need to manage timing it. Is there some mechanism for that in SimpleNGen? Thanks, Jason

#16 Chris Walker

Chris Walker

    Secret Labs Staff

  • Moderators
  • 7767 posts
  • LocationNew York, NY

Posted 07 August 2011 - 04:49 PM

Once .NET MF 4.2 (final version) ships, we can build a few special builds of it with various features. That should be sometime in late August or September. Jason--are there NETMF 4.2 features you need, or can you use Corey's NETMF 4.1-based version in the meantime? Chris

#17 Corey Kosak

Corey Kosak

    Advanced Member

  • Members
  • PipPipPip
  • 276 posts
  • LocationHoboken, NJ

Posted 07 August 2011 - 04:51 PM

I wish I knew the answer to this. Unfortunately I am not an expert in the firmware. I had previously asked if anyone could help by pointing me to or creating sample C++ code that I could then adapt to SimpleNGen style, but I have not any luck in this area.

#18 CW2

CW2

    Advanced Member

  • Members
  • PipPipPip
  • 1592 posts
  • LocationCzech Republic

Posted 07 August 2011 - 05:55 PM

The protocols I am interested in are time based, with no shared clock - so for example I need to trigger a 38kHZ carrier signal (generated by a PWM) for ~600 microseconds.

Just out of curiosity, are you looking for something like the modulated PWM ?

#19 JasonS

JasonS

    New Member

  • Members
  • Pip
  • 3 posts

Posted 08 August 2011 - 03:39 AM

Jason--are there NETMF 4.2 features you need, or can you use Corey's NETMF 4.1-based version in the meantime?


4.1 Is fine for me - my understanding was that Corey's 4.1-based version is for the base Netduino only - unfortunately, I only have a few of the Pro - Ethernet is important for my project. Is that not the case?

I wish I knew the answer to this. Unfortunately I am not an expert in the firmware. I had previously asked if anyone could help by pointing me to or creating sample C++ code that I could then adapt to SimpleNGen style, but I have not any luck in this area.


I will poke around as well, and see if I can find anything. I think there is a lot of utility in being able to time things running in native mode, instead of strictly running at "max speed".

Just out of curiosity, are you looking for something like the modulated PWM ?


Yes! That is exactly what I am trying to implement (the long way around) - I was going to use 2 pins ANDed together, the 38kHZ PWM and a second pin with the data. This requires me to drive the second PIN faster than I can directly on the netduino. I have voted for it on codeplex.

Thanks!

#20 JasonS

JasonS

    New Member

  • Members
  • Pip
  • 3 posts

Posted 11 August 2011 - 08:44 PM

I will poke around as well, and see if I can find anything. I think there is a lot of utility in being able to time things running in native mode, instead of strictly running at "max speed".


Sorry to self-reply, but I may have found something useful - assuming that my understanding of SimpleNGen and wanderings through .NETMF have lead me in the correct direction.

My understanding of SimpleNGen is that it is generating opcodes for the processor, sticking them into an array, and then moving the IP to the beginning of that array when called. So, I would assume then that what you would need for timing is some sort of delay instruction block which your compiler could generate based on some function call which you compiled away.

I browsed through the .NETMF source (Specifically, starting at the new OneWire implementation - since I knew it required sub ms timings). It made a series of calls (usDelay in the OneWire library), which eventually ended up at AT91_TIME_Driver::Sleep_uSec() in the .NETMF code for the AT91 hardware (I assumed that this is the correct hardware for NetDuino).

This method is in the .NETMF 4.2 codebase at: client_v4_2_comm/DeviceCode/Targets/Native/AT91/DeviceCode/AT91_TIME/AT91_TIME.cpp

The code is here:

void __section(SectionForFlashOperations) AT91_TIME_Driver::Sleep_uSec( UINT32 uSec )
{
    GLOBAL_LOCK(irq);

    UINT32 value   = AT91_TIMER_Driver::ReadCounter( AT91_TIMER_Driver::c_SystemTimer );
    UINT32 maxDiff  = CPU_MicrosecondsToTicks( uSec );      // The free-running timer clocks at a constant 3.25 MHz

    if(maxDiff <= AT91_SLEEP_USEC_FIXED_OVERHEAD_CLOCKS) maxDiff  = AT91_SLEEP_USEC_FIXED_OVERHEAD_CLOCKS;
    else                                                 maxDiff -= AT91_SLEEP_USEC_FIXED_OVERHEAD_CLOCKS;

    while((AT91_TIMER_Driver::ReadCounter( AT91_TIMER_Driver::c_SystemTimer ) - value) <= maxDiff);
}

Actually translating this into something directly useful to SimpleNGen is unfortunately beyond my knowledge of this hardware, firmware or memory layout. I am happy to break this into some slightly more useful code, if that is helpful, with things like actual memory addresses and constants instead of names - let me know. This is as far as I could get with notepad and grep on my work machine - pulling this all into an actual IDE will make it easier.

Hope this is generally the right direction!

--Jason




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

home    hardware    projects    downloads    community    where to buy    contact Copyright © 2016 Wilderness Labs Inc.  |  Legal   |   CC BY-SA
This webpage is licensed under a Creative Commons Attribution-ShareAlike License.