Code Highlighting

Tuesday, December 16, 2014

Ladies and gentlemen: salt your passwords

A few weeks ago I recovered the database of an old website from backup. The customer wanted the old contact info and had lost its own backup.
The old database hashed its passwords (SHA-1), but did not salt them. Looking at the old users table, I wondered how well the rainbow table approach would work - using Google as a big rainbow table. Just feed the hash into the search field and see what comes up.

Here are the results:
PasswordClear textCount
7C4A8D09CA3762AF61E59520943DC26494F8941B12345636
9C2028963DC9F7FBB4CB30140428A210C61DBB2Cwachtwoord24
9CF95DACD226DCF43DA376CDB6CBBA7035218921azerty22
62E839476B23E579EFB96B47391599FFCA4CFA94?18
7110EDA4D09E062AA5E4A390B0A572AC0D2C0220123418
F001F2E438738807D3079BFFAF66519B9D0F26C7azqswx16
F7C3BC1D808E04732ADF679965CCC34CA7AE344112345678916
D18C9E9DCCE902D6A3E21E72BADA443AC294CB5FPaswoord15
FDA48D6A63F351DC46D411336DE4BA33F77B66F5voetbal14
D22BC6BAD61129B636AFFA2511B3CE522CD74BB3brecht13
EE8D8728F435FD550F83852AABAB5234CE1DA528iloveyou12
48F285F9A1E15CB6240506182A3C08AEDD639F26dansen11

The count indicates how many users chose that password. Users spoke dutch, used an azerty keyboard. Of the top 12, I found all but 1 using a Google search. This is why you salt your passwords.

Mind you, it's also a reason to implement a decent password policy. One that does not allow '1234'.

I really wonder about that 1 that I wasn't able to find though. Must be some dutch word.

Friday, September 5, 2014

OutputCache on User Controls - VaryByControl

A question on stackoverflow prompted me to research this. Initially a code sample was included, showing how this user was trying to set up cache variation by property value. The VaryByControl parameter was set to the name of this property. This appeared to work for property values entered in markup, but failed if the property was set to a variable: the control bound to the property only ever showed the first value is was bound to.

I set up a test project to attempt to reproduce the problem, and saw identical behavior. So far so good.

<!-- the aspx page, the Number property is set to a random number -->
<%@ Register Src="~/UserControls/Test.ascx" TagPrefix="uc1" TagName="Test" %>

<asp:Content runat="server" ID="BodyContent" ContentPlaceHolderID="MainContent">
    <uc1:Test runat="server" ID="Test1" Number="1" />
    <uc1:Test runat="server" ID="Test2" Number="2" />
    <uc1:Test runat="server" ID="Test3" Number="<%# Number %>" />

    <asp:Label runat="server" Text="<%# Number %>"></asp:Label>
</asp:Content>

<!-- the user control -->
<%@ OutputCache Duration="180" VaryByControl="Number" VaryByParam="None" Shared="true" %>

<h1><%# Number  %></h1>


Detective hats everyone! Let's investigate how outputcache for user controls works!

First the code generation for user controls. An attribute is applied to the generated class that contains the caching parameters:

    [System.Web.UI.PartialCachingAttribute(180, null, "Number", null, null, true, ProviderName = null)]
    public class usercontrols_test_ascx : global::TestOutputCache.UserControls.Test

The parser for the page checks user controls for the caching attribute and - if present - creates a PartialCachingControl, passes it the caching parameters, control ID and a control builder delegate:

    System.Web.UI.StaticPartialCachingControl.BuildCachedControl(@__ctrl, "Test1", "50114342", 180, null, "Number", null, null, new System.Web.UI.BuildMethod(this.@__BuildControlTest1), null);

Inside the PartialCachingControl, a hash is calculated based on the variation parameters, and the cache is checked for the hash. A cache miss results in the delegate being called, and the results getting stored in cache.
Here is the relevant portion of the hash calculation routine:

        if (cachedVary._varyByControls != null) {

            // Prepend them with a prefix to make them fully qualified
            string prefix;
            if (NamingContainer == Page) {
                // No prefix if it's the page
                prefix = String.Empty;
            }
            else {
                prefix = NamingContainer.UniqueID;
                Debug.Assert(!String.IsNullOrEmpty(prefix));
                prefix += IdSeparator;
            }

            prefix += _ctrlID + IdSeparator;

            // Add all the relative vary params and their values to the hash code
            foreach (string varyByParam in cachedVary._varyByControls) {

                string temp = prefix + varyByParam.Trim();
                combinedHashCode.AddCaseInsensitiveString(temp);
                string val = reqValCollection[temp];
                if (val != null)
                    combinedHashCode.AddObject(reqValCollection[temp]);
            }
        }


Variable "reqValCollection" is a dictionary of POST values (if there are any) or GET values.
And the first question presents itself, because the VaryByControl only varies by POST values corresponding with the controls specified. The property value cannot matter: it is never read.

In fact; when deciding to server the cached markup or not, the control has not been created yet, and may not ever be. That's the entire point of the output caching. Obviously variation by Property value doesn't make sense.

So why does it ever work?

Back to the test project to confirm hypothesis by setting VaryByControl to something else.
<%@ OutputCache Duration="180" VaryByControl="PorkPies" VaryByParam="None" Shared="true" %>

<h1><%# Number  %></h1>

Yup. Everything still works identically to how it worked before. The value of VaryByControl does not matter, as long as there is a value. Dropping the VaryByControls entirely shows normal behavior: one single cached version being served for each request.

Smells like a bug! Lets see if we can find it!

In fact, if you look up to the code I posted, the bug is right there. The "temp" variable contains the unique id of the user control. I imagine this field is added to prevent a cache collision for two controls - both specified in VaryByControl - with identical values. But it is added to the combinedHashCode even before it is verified to have a value in reqValCollection. It still works because the HashCodeCombiner class generates a different hash for the same objects added in a different order - it does not simply xor everything and calls it a day.
That means User Control OutPutCache has a built-in variation for:

  • Control ID, and
  • NamingContainer ID
You can activate it by setting VaryByControl to any value whatsoever. I would argue that the correct code looks like this:

            // Add all the relative vary params and their values to the hash code
            foreach (string varyByParam in cachedVary._varyByControls) {

                string temp = prefix + varyByParam.Trim();
                string val = reqValCollection[temp];
                if (val != null){
                    combinedHashCode.AddCaseInsensitiveString(varyByParam.Trim());
                    combinedHashCode.AddObject(reqValCollection[temp]);
                }
            }

Perhaps there is a good reason to include the ID and naming container in the cache key, but it does not make sense to me.

I don't expect Microsoft will ever fix this bug; it would break a multitude of sites in very ugly ways. I'm guessing they've found it before, and decided to leave well enough alone.

Thursday, July 3, 2014

What if events in C# were, you know, cooler?

In the beginning events in C# were awesome. Some of us came from Java, and used to have to implement interfaces named IButtonClickListener on some inner classes whatever nonsense just to react to some button being clicked, but not in C#. No, in C# you just did the following:

    public partial class Form1 : Form
    {
        Button newButton;

        public Form1()
        {
            InitializeComponent();

            newButton = new Button()
            {
                Text = "Click me!",
                Left = 20,
                Top = 20
            };

            newButton.Click += new EventHandler(HandleClick);

            this.Controls.Add(newButton);
        }

        private void HandleClick(object sender, EventArgs e)
        {
            MessageBox.Show("Hi there!");

            newButton.Click -= HandleClick;
        }
    }

No obnoxious interface nonsense! Delegates! The future is now!

But over 10 years later we have gotten spoiled with anonymous delegates and lambdas, and all of a sudden the C# event model does not seem so cool anymore. Because when you hook up an event handler like this:

newButton.Click += (sender, e) => MessageBox.Show("Hi there!");

do you imagine you can remove it like this:

// fugetaboutit!
newButton.Click -= (sender, e) => MessageBox.Show("Hi there!");

No way! You would have to save the handler to a variable to have a reference handy to be able to remove
the handler later:
EventHandler handler = (sender, e) => MessageBox.Show("Hi there!");

Worse! Microsoft added lots of nice generic delegate types Action<T>, Action<T1, T2>, Action<T1, T2, T3> etc that we can't use because we're stuck with the EventHandler delegate types for Events. You would need a wrapper around the Invoke function to make that work.

Would you like to check out what is currently hooked up to your event? Tough!

Clear the whole thing and start over? Get outta here!

But despair no more! I have written a half-assed solution that I think might have been marginally better if it had worked properly!

Presenting: the new and improved Event:


    public class Event<TEventArgs,TEventHandler>
        where TEventArgs : EventArgs
        where TEventHandler : class
    {
        // the main store for handlers
        private Dictionary<int, Action<object, TEventArgs>> handlers =
            new Dictionary<int, Action<object, TEventArgs>>();

        // a dictionary that maps the original handlers to the generated wrappers
        private Dictionary<object, int> operatorAddedHandlers =
            new Dictionary<object, int>();

        public Event()
        {
        }

        static Event()
        {
            // check if my TEventHandler type parameter is a delegate type
            // where TEventHandler : Delegate is not supported
            if (!typeof(TEventHandler).IsSubclassOf(typeof(Delegate)))
            {
                throw new InvalidOperationException(typeof(TEventHandler).Name + " in generic type parameter TEventHandler is not a delegate type.");
            }
        }

        /// <summary>
        /// Maps events of the same name on the container object to the Event field that hides it
        /// </summary>
        /// <param name="eventGenerator">the object that contains the Event field (typically this)</param>
        public void CaptureBaseEvents(object eventGenerator)
        {
            var fieldNames = new List<String>();
            var classType = eventGenerator.GetType();
            var fields = classType.GetFields();
            
            // check which field the current instance has been assigned to, store the name
            foreach (var field in fields)
            {
                var val = field.GetValue(eventGenerator);
                if (Object.Equals(val, this))
                {
                    fieldNames.Add(field.Name);
                }
            }

            // get a MethodInfo for this class's Invoke method
            var invokeHandler =
                typeof(Event<TEventArgs, TEventHandler>).GetMethod("Invoke");

            // check if any base events exist that have the same name
            // if so, hook up our Invoke method
            foreach (var fieldName in fieldNames)
            {
                var classEvent = classType.GetEvent(fieldName);

                if (classEvent != null)
                {
                    var tDelegate = classEvent.EventHandlerType;
                    var d = Delegate.CreateDelegate(tDelegate, this, invokeHandler);

                    var addHandler = classEvent.GetAddMethod();
                    Object[] addHandlerArgs = { d };
                    addHandler.Invoke(eventGenerator, addHandlerArgs);
                }
            }
        }

        /// <summary>
        /// Invokes the event handlers
        /// </summary>
        /// <param name="sender">The object that triggered the event</param>
        /// <param name="e">The event parameters</param>
        public void Invoke(object sender, TEventArgs e)
        {
            // just in case a handler modifies the handlers
            var handlerDelegates = handlers.Select(hs => hs.Value).ToList();

            foreach (var handler in handlerDelegates)
            {
                handler.Invoke(sender, e);
            }
        }

        /// <summary>
        /// Removes all handlers
        /// </summary>
        public void ClearHandlers()
        {
            handlers.Clear();
        }

        /// <summary>
        /// Gets a list of all handlers and their removal token
        /// </summary>
        /// <returns></returns>
        public IEnumerable<EventHandlerSet<TEventArgs>> GetAllHandlers()
        {
            // store in list in case someone loops through to find a handler to remove
            // that seems kind of likely
            var handlerSets = handlers.Select(hs => new EventHandlerSet<TEventArgs>()
            {
                Handler = hs.Value,
                RemovalToken = hs.Key
            }).ToList();

            return handlerSets;
        }

        /// <summary>
        /// Adds an event handler
        /// </summary>
        /// <param name="newHandler">The new handler to add</param>
        /// <returns>The removal token for the newly added handler</returns>
        public int AddHandler(Action<object, TEventArgs> newHandler)
        {
            // we don't hook up the same handler twice,
            // just return its current removal token
            if (handlers.Any(ks => ks.Value.Equals(newHandler)))
            {
                return handlers.Where(ks => ks.Value.Equals(newHandler)).Single().Key;
            }

            // use a new guid cut off at int32 length for key generator
            var newGuid = Guid.NewGuid();
            int newKey = BitConverter.ToInt32(newGuid.ToByteArray(), 0);

            // it's a lot more likely at 32 bits
            while (handlers.ContainsKey(newKey))
            {
                newGuid = Guid.NewGuid();
                newKey = BitConverter.ToInt32(newGuid.ToByteArray(), 0);
            }

            handlers.Add(newKey, newHandler);

            return newKey;
        }

        /// <summary>
        /// Adds a new handler to the Event field
        /// </summary>
        /// <param name="thisEvent">The event field</param>
        /// <param name="newHandler">The handler to add</param>
        /// <returns></returns>
        public static Event<TEventArgs, TEventHandler> operator +(Event<TEventArgs, TEventHandler> thisEvent, TEventHandler newHandler)
        {
            var handlerDelegate = newHandler as Delegate;

            if (handlerDelegate == null)
                throw new InvalidOperationException("Handler is not a delegate type!");

            // if this handler has already been added, do nothing
            if(thisEvent.operatorAddedHandlers.ContainsKey(newHandler)){
                return thisEvent;
            }

            var removalToken = thisEvent.AddHandler(delegate(object sender, TEventArgs e)
            {
                handlerDelegate.DynamicInvoke(new object[] { sender, e });
            });

            thisEvent.operatorAddedHandlers.Add(newHandler, removalToken);

            return thisEvent;
        }

        /// <summary>
        /// Removes the specified handler
        /// </summary>
        /// <param name="handler">The handler to remove</param>
        public void RemoveHandler(Action<object, TEventArgs> handler)
        {
            if (handlers.Any(ks => ks.Value.Equals(handler)))
            {
                var removalToken = handlers.Where(ks => ks.Value.Equals(handler)).Single().Key;

                handlers.Remove(removalToken);
            }
        }

        /// <summary>
        /// Removes the specified handler
        /// </summary>
        /// <param name="removalToken">The handler's removal token</param>
        public void RemoveHandler(int removalToken)
        {
            if (handlers.ContainsKey(removalToken))
                handlers.Remove(removalToken);
        }

        /// <summary>
        /// Removes the specified handler
        /// </summary>
        /// <param name="thisEvent">The event field</param>
        /// <param name="handler">The handler to remove</param>
        /// <returns></returns>
        public static Event<TEventArgs, TEventHandler> operator -(Event<TEventArgs, TEventHandler> thisEvent, TEventHandler handler)
        {
            if (!thisEvent.operatorAddedHandlers.ContainsKey(handler))
                return thisEvent;

            var removalToken = thisEvent.operatorAddedHandlers[handler];

            thisEvent.RemoveHandler(removalToken);

            return thisEvent;
        }
    }

    public class EventHandlerSet<TEventArgs>
    {
        internal EventHandlerSet() { }
        public int RemovalToken { get; set; }
        public Action<object, TEventArgs> Handler { get; set; }
    }

I've made it so that it's mostly a drop-in replacement for pre-existing events. Obviously you need to inherit from the class implementing the events. So let's take that boring old button we had, and jazz up the click event:


    public class NewAndImprovedButton : System.Windows.Forms.Button
    {
        public NewAndImprovedButton()
            : base()
        {
            Click.CaptureBaseEvents(this);
        }

        public new Menno.Event.Event<EventArgs, EventHandler> Click = new Menno.Event.Event<EventArgs, EventHandler>();
    }

Turns out you can hide an event with a field. Who knew? Also, the CaptureBaseEvents in the constructor only works because fields are initialized before the constructor runs. Otherwise I'd have had to do something odd and confusing. More so.

If we take the first piece of code and replace Button by NewAndImprovedButton, like so:
    public partial class Form1 : Form
    {
        NewAndImprovedButton newButton;

        public Form1()
        {
            InitializeComponent();

            newButton = new NewAndImprovedButton()
            {
                Text = "Click me!",
                Left = 20,
                Top = 20
            };

            newButton.Click += new EventHandler(HandleClick);

            this.Controls.Add(newButton);
        }

        private void HandleClick(object sender, EventArgs e)
        {
            MessageBox.Show("Hi there!");

            newButton.Click -= HandleClick;
        }
    }

Everything keeps working exactly the way it did. I implemented the + and - operators to mirror the current Event syntax, and the CaptureBaseEvents method hooks up the event in the base class that the field hides to the Invoke method. Magic!
But we did not make this to keep working the same way. Here's what's new:

  • an AddHandler method that takes an Action<object, TEventArgs> and returns an int that functions as a token.
  • (obviously) a RemoveHandler that an int token.
  • for good measure: a RemoveHandler that takes an Action<object, TEventArgs>
  • a ClearHandlers method
  • a GetAllHandlers method that returns all handler delegates and their tokens, even the ones added through reflection.
Of course there are some rough edges too:
  • Field cannot be readonly if you use the operators. Anything could happen.
  • Operators generate wrappers through reflection. Performance is bound to be questionable.
  • Probably hundreds of corner cases I haven't considered.
Still, now you can do this:

            int removalToken = 0;
            removalToken = newButton.Click.AddHandler((sender, e) =>
            {
                MessageBox.Show("Hi there!");
                newButton.Click.RemoveHandler(removalToken);
            });

For some folks, that's worth a few rough edges.

Sunday, August 18, 2013

What if performance was more important than accuracy?

In 2000 Interplay released a game called "Messiah". It wasn't a particularly good game, and the only reason I mention it is it had this automatic system for scaling detail levels. Rather than letting people set detail level manually, it would detect when it could add some more polygons, and when detail levels needed to be dialled down. That way the game could fairly consistently hit the target frames per second.

That got me wondering: what if you find yourself programming something for which being fast is more important than being exactly right?
This is not an entirely unfamiliar trade-off: everytime you use a double instead of a decimal you decide that fast calculations are more important than exact decimal representation of your numbers. And the UDP protocol foregoes transmission verification for speed.

In the past we would write asynchonous function calls somewhat like this:
(Now with async/await, things are different again. Well, they look different.)

// Start reading from that slow file system
var fileStream = new System.IO.FileStream(@"C:\blablah", System.IO.FileMode.Open, System.IO.FileAccess.Read);
var asyncResult = fileStream.BeginRead(blahblah ...);

// Do lots of stuff in between to maximize your efficiency

// And now you just need your data, so for the rest of the 
// time you're synchronously waiting for it to arrive
fileStream.EndRead(asyncResult);

That's fine and dandy if you're just reading data. But what if you're calculating something on another thread, and you've already found your result, but the caller hasn't asked for it yet? Maybe you could spend your time improving your result rather than twiddling your thumbs.
So we need a method that iteratively improves on its previous results, and returns each so that we have something to return. Obviously I chose pi (using Microsoft.SolverFoundation.Common):
(using BBP formula)

static IEnumerable<Rational> GetPi()
{
    Rational bigPi = new Rational();
    Rational bigMinusOne = -1;
    Rational bigOne = 1;
    Rational bigTwo = 2;
    Rational bigFour = 4;
    Rational bigFive = 5;
    Rational bigSix = 6;
    Rational bigEight = 8;
    Rational bigSixteen = 16;
    for (int i = 0; i < 10000; i++)
    {
        Rational bigI = i;
        Rational powI;
        Rational.Power(16, i, out powI);
        var bigS = (bigOne / powI) * (bigFour / ((bigEight * bigI) + bigOne) - (bigTwo / ((bigEight * bigI) + bigFour)) - (bigOne / ((bigEight * bigI) + bigFive)) - (bigOne / ((bigEight * bigI) + bigSix)));
        bigPi += bigS;
        // We don't want to return anything less than 7 hexadecimal digits
        if (i > 7)
            yield return bigPi;
    }
}

Sooo, up to ten thousand hexadecimal digits (hexits?) of pi generated as a decimal fraction. Now to write a wrapper class that runs this in a loop in another thread:

public sealed class IncreasinglyAccurate<T>
{
    private Func<IEnumerable<T>> _generator;
    private Thread _generatorThread;
    private bool _hasValue = false;
    private T _currentValue;
    public IncreasinglyAccurate(Func<IEnumerable<T>> generator)
    {
        if (generator == null)
            throw new ArgumentNullException("generator");
        _generator = generator;
        // returns as soon as the generator thread is started
        GetValues();
    }
    private void GetValues()
    {
        // Spinning up a new thread is wasteful, but I can't set priority
        // on work items added to the threadpool
        _generatorThread = new Thread(delegate()
        {
            foreach(T value in _generator()){
                _currentValue = value;
                _hasValue = true;
            }
        });
        _generatorThread.Priority = ThreadPriority.BelowNormal;
        _generatorThread.Start();
    }
    public T GetValue()
    {
        // wait for a value
        while (!_hasValue)
        {
            Thread.Sleep(1);
        }
        // delegates will need to expect a ThreadAbortException
        _generatorThread.Abort();
        _generatorThread.Join();
        return _currentValue;
    }
}
/// <summary>
/// Little wrapper to get generic type inference
/// </summary>
public static class IncreasingAccuracy
{
    public static IncreasinglyAccurate<S> FromDelegate<S>(Func<IEnumerable<S>> generator)
    {
        return new IncreasinglyAccurate<S>(generator);
    }
}

That looks about right. Now we should be able to use this as follows:

var piGenerator = IncreasingAccuracy.FromDelegate(GetPi);
// Do some work!
System.Threading.Thread.Sleep(50);
Console.Write(piGenerator.GetValue().ToString());

On my slow old computer that shows a very big number divided by another big number (probably a power of 16!). Increasing the sleep time increases the size of the number, so that looks right.

I'll grant you that pi digits are not that useful; I'm not sure when you would ever need more than, oh, 10 digits max. But I can think of some situations where it's useful to have a sufficient answer fast, but to keep thinking about a better one: AI, voice recognition, anything that will not be 100% perfect in a hurry.

Thursday, June 13, 2013

Something silly

I've been spending some of my free time working on something silly. People who know me expect me to bring up the OMGWTF2 contest now. That's a valid point, so let me start over.

I've been spending some of my free time working on two silly somethings. Here's a link to one of those: http://demo.tabeoka.be/Contact%20%20Tabeoka.htm . Click that link and fill out the form and send it up.
Go ahead, nothing bad will happen. I'll wait right here.






Did you click that link? No? You need to have clicked that link to make sense of the rest of this post. No really! Go back and click.






Right. So now that that is done, I have a second link for you: click right here.
Now there are three possibilities:
1) you're pretty gullible, and thought that was amazing,
2) you thought that was still pretty neat, or
3) that link did nothing because you're using some browser I haven't tested, which are many.

For those of you who chose option 3 and missed all the excitement: that second link should have replayed exactly what you did on that page the first time you were there. I had the idea after going through some Google Analytics graphs and wondering: "But why do they click that particular link?". You could potentially use this type of script to do usability testing on the cheap.
The code is for the most part pretty straightforward, but there are a few things which I thought were interesting to point out:

It generates unique selectors for elements. If you click something, it needs to log which element. When you're just dealing with javascript, you would keep a reference to the DOM element, but we're logging to json. Generating a jquery selector enables getting an easy reference to the clicked element. For now I'm generating a selector by going through parent elements ( td>tr ) and logging the index (:nth-child) until I hit an element with an id (#content) or the document root (html>body>). Amazingly I had to write this myself; I couldn't find a pre-written script on Google.

In the interest of keeping bandwidth use and file size down, I log  frame-by-frame. Every 40 ms (for a frame rate of 25) the data collector comes by, compiles and documentEvents object and adds it to the array. which brings me to the next point: this script is completely modular. Currently it logs input fields, mouse location, scroll position and clicks. If you want to add another thing to log though, say actions in a Flash object, you just write another set of methods to log and replay those, and point the main logger file to it. Remember that every additional logger adds extra bytes to the data that needs to be sent to the server.

Everybody knows that the onunload (or onbeforeunload) can not be trusted. That's why I ping the latest frames to the server every second. You could set it to 2 seconds or 10 seconds or whatever as well. At the server end I have a .NET handler that appends the extra json to the end of a file. The first request generates a new file and sends back the id for subsequent requests (currently a Guid). This would be trivial to implement in another server language.

Current problems include:
In Chrome onchange on an input field is only fired after the field loses focus. IE fires it on keypress. That means that in IE you see the text field value being typed up, but in Chrome it just appears fully written. Chrome is better for bandwidth, but IE is nicer to see replayed. I haven't made up my mind yet which is preferable.

Replaying the logged event mutates the initial page state, but moving back the timeline does not revert to previous page state. I could clear text fields and such, but simulated clicks that fired event handlers might be impossible to undo. Like that cookie notice.

Lastly, this is just some demo script code, don't use it for anything serious. I haven't figured out yet if I'm going to actually release this code as open source at e.g. GitHub. Don't copy/paste and run with it. I'm sure it's illegal or something.

Tuesday, May 7, 2013

Short: belgian rijksregisternummer validation in javascript

It's been really busy, so no time for blog posts. In the meantime, here is a short function to validate id card numbers (rijksregisternummer) in Belgium, according to the official guidelines. I could not find a proper implementation of this in javascript.

        function IsRRNoValid(n) {
            // RR numbers need to be 11 chars long
            if (n.length != 11)
                return false;

            var checkDigit = n.substr(n.length - 2, 2);
            var modFunction = function(nr) { return 97 - (nr % 97); };
            var nrToCheck = parseInt(n.substr(0, 9));
            
            // first check without 2
            if (modFunction(nrToCheck) == checkDigit)
                return true;

            // then check with 2 appended for y2k+ births
            nrToCheck = parseInt('2' + n.substr(0, 9));

            return (modFunction(nrToCheck) == checkDigit);
        }

Easy as pie. You can get the gender and date of birth out of there as well, but I don't need that info for my purpose. A slightly more advanced validation would also check to see if the first 6 digits represent a valid date according to the yyMMdd format (determining the right century using the current validation).

Monday, March 4, 2013

Good news! People are smart! Kind of!

For customer HAROL we wrote a little memory game. There are 16 cards (8 pairs), and you get 3 attempts to try and find a match. If you do find a match you might just win an iPad! If you don't - well, you still get a discount coupon. The game was played on iPads set up at Batibouw. There is no online link for the game, or I'd link you there *.

Before we sent the game off to Batibouw, I sat down to calculate the likelihood of finding a match within your three attempts: it shouldn't be too hard or Harol would never get rid of its iPads. For calculations, I would assume a 100% perfect memory. The most interesting part here is how close people would get to that 100% perfect memory score. Are people smart? Kind of? Or are they really dumb?

I haven' t had a lot of formal statistics training, so I've largely relied on The Big Three: "simple common sense", "blatant disregard for other people's opinions" and "shameless guessing". Readers with a background in statistics: feel free to set me on the right path in the comments. I'll feel free to blatantly disregard you.
Anyway, here's what I figured:

Three turns, six cards. Rather than calculate the 'winning' percentage, I'll calculate the 'losing' percentage, and deduct from 100 %. Losing is the one route you take through the game where you don't find a match, winning is any of 3 distinct events - maybe even 5.
  • Card 1: nothing to do here
  • Card 2: Lucky guess chance to win. Chances to lose: 14/15
  • Card 3: May be a match for one of the 2 previous ones. 12/14 it ain't though.
  • Card 4: And if it ain't, there's still a lucky guess chance: 12/13
  • Card 5: A match for any of the previous ones is starting to be likely, but not quite: 8/12
  • Card 6: Last chance to hit a match: 10/11
So where does that put us? Far as I can see, we just multiply all of those fractions, and come up with the losing percentage: 0,4475524475524476. Say 45%. You're actually 55% likely to win if you play it smart. (If you just guess blindly, your winning chances are obviously (1-pow(14/15, 3)) = 18.6 % = not looking good).

So how did people do?




**** drumroll ****




49%
Only 6% away from a perfect memory.

Good news! People are smart! Kind of!



* For those of you who care: it was an MVC app, some nice ajax, css transitions that I could afford to rely on, as it only needed to work on iPad. Who knows maybe it will be recycled for another promotion that will run online.

Thursday, January 17, 2013

Pixels are dead.

And Apple killed them.

Well, they're not really dead: I'm sure that in the foreseeable future images will still be rendered onto a pixel-based (or semi-pixel based) screen of sorts. In css though, it is time to say goodbye: you shouldn't use pixels anymore. But don't worry: you don't anyway. Don't fool yourself into thinking css pixels necessarily translate 1:1 to actual pixels on an actual screen.


Allow me to demonstrate


Css3 defines the newfangled concept of a resolution unit. It can be set to the traditional dpi, dpcm (if you're a metric-nazi) or dppx (dots per pixel. That's right, dots per pixel). And just like that css formalizes what tablets and smartphones have been doing for a long time: the css pixel is now an abstraction.
Actually, according to the css standard, pixels have been defined as 1/96th of an inch , for a while now. For convenience sake though (and who can blame them?), browsers have been equating the css pixel with the actual pixel for all this time. If that meant redefining the length of the inch, so be it. It's not like Windows actually knows the size of an inch on your screen anyway. How could they, and still support every no-name brand Korean monitor on the market? By necessity, Apple can not do any better.


But pixels are pixels!


If you are the lucky owner of an iPhone 5, you have a 1136 x 640 screen in a 4" size. That leads to 1136 / (sqrt(pow(4, 2) / (pow(16, 2) + pow(9, 2)) * 16) = 325.846 ppi. So if I defined a font size of, say, 13px, in my css that would mean letters would be just over 1mm tall on the iPhone. For my American readers: that's very small ( about 4/100ths of an inch). Reading would be a wee bit hard on the eyes.
So mobile Safari doesn't do that. Instead it creates a virtual viewport that is even wider by default (980px), but also allows you to pick the size of your virtual viewport using meta tags.  It will also adjust the font size to not be ridiculously tiny. Android uses much the same meta tags - both use WebKit after all.


It's all taken care of! Thanks Apple! Let's have a beer and forget about it.


All this stuff makes it easy to create a site that will look decent on iPhone and iPad. Add a couple of media queries to make your website more responsive and call it a day. Your html is sized to your viewport, and then rendered to the high resolution screen, so text remains nice and crisp.
One item that remains though are the images. If you set your img size to 300 by 200, you probably also uploaded a image file with dimensions 300 by 200. But remember: the pixel is a lie. If you set your viewport low enough though, there are enough (physical) pixels there to render an image with a much higher resolution.    Css 4 is working hard to take care of this.


What am I supposed to do?


I have no idea. In a perfect world, I think we should combine physical measurements with percentages, and use media queries based on physical size. No platform properly supports the physical units though; a simple test confirmed that. Tablets could support this: they know the size of their screens perfectly. If they did render and inch to an inch though, a point would have to be a inch/72, and a pixel inch/96, and everything would be broken. Chicken and egg. It'd be nice if there was an opt-in meta tag or something similar for real physical measurements. Because pixels are dead.

Friday, December 28, 2012

SELECTing the comedy horror genre

Whenever we get a new intern, I like to poke and prod him*, to see what he's made of (bones and gooey bits, usually). To test SQL proficiency, I use the following problem. I like it because it's something that comes up occasionally in projects, and is surprisingly complex, though it seems like it shouldn't be:

Suppose you've got a movie database. You've got a table with movies T_MOVIES:

CREATE TABLE [dbo].[T_MOVIES](
 [movie_key] [int] NOT NULL,
 [movie_name] [nvarchar](500) NOT NULL,
 CONSTRAINT [PK_T_MOVIES] PRIMARY KEY CLUSTERED 
(
 [movie_key] ASC
)WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]

and there's also a table for movie genres T_GENRES:

CREATE TABLE [dbo].[T_GENRES](
 [genre_key] [int] NOT NULL,
 [genre_name] [nvarchar](500) NOT NULL,
 CONSTRAINT [PK_T_GENRES] PRIMARY KEY CLUSTERED 
(
 [genre_key] ASC
)WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]

To link both tables there is a third table T_MOVIE_GENRES:

CREATE TABLE [dbo].[T_MOVIE_GENRES](
 [movie_key] [int] NOT NULL,
 [genre_key] [int] NOT NULL,
 CONSTRAINT [PK_T_MOVIE_GENRES] PRIMARY KEY CLUSTERED 
(
 [movie_key] ASC,
 [genre_key] ASC
)WITH (IGNORE_DUP_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]

Assume the proper foreign key constraints have been applied, and you have a pretty sensible lay-out. To select all movies within the horror genre you only have to join T_MOVIES to T_MOVIE_GENRES and filter down your genre key in the WHERE clause to whatever the horror genre is, suppose it's 5:

SELECT
 T_MOVIES.movie_key,
 T_MOVIES.movie_name
FROM
 T_MOVIES INNER JOIN
 T_MOVIE_GENRES ON
 T_MOVIES.movie_key = T_MOVIE_GENRES.movie_key
WHERE
 T_MOVIE_GENRES.genre_key = 5

The question now is: What if I want to filter by two genres? How do I find movies that are not only horror, but also comedy? What query will yield "Shaun of the Dead"?
More generally, how do we find those records in a table that have more than one matching record in another table, where those matching records have a field set to a set of specific values?

Obviously WHERE T_MOVIE_GENRES.genre_key IN (1,5) is going to yield movies that belong to either genre.
At this point usually the intern scratches his chin, gives it a bit of thought, and comes up with this:

SELECT
 T_MOVIES.movie_key,
 T_MOVIES.movie_name
FROM
 T_MOVIES INNER JOIN
 (
 SELECT  T_MOVIE_GENRES.movie_key
 FROM T_MOVIE_GENRES
 WHERE T_MOVIE_GENRES.genre_key = 5
 ) AS Q_HORROR
 ON T_MOVIES.movie_key = Q_HORROR.movie_key
  INNER JOIN
 (
 SELECT  T_MOVIE_GENRES.movie_key
 FROM T_MOVIE_GENRES
 WHERE T_MOVIE_GENRES.genre_key = 1
 ) AS Q_COMEDY
 ON T_MOVIES.movie_key = Q_COMEDY.movie_key

(Or some other solution involving a subquery)
Okay, fine, you found "Shaun of the Dead". But what if I'm actually in the mood for Zombieland, a comedy / horror / road movie? In fact, I want a stored procedure that can take an arbitrary number of genres, and filter by it. You can go the dynamic sql route, and build a string with an arbitrary number of subqueries. It'd be ugly and hard to maintain, but it would work.
The following shows what I think is the best solution though:

SELECT
 T_MOVIES.movie_key,
 T_MOVIES.movie_name
FROM
 T_MOVIES INNER JOIN
 T_MOVIE_GENRES
 ON T_MOVIES.movie_key = T_MOVIE_GENRES.movie_key
WHERE
 T_MOVIE_GENRES.genre_key in (1,5)
GROUP BY
 T_MOVIES.movie_key,
 T_MOVIES.movie_name
HAVING
 COUNT(*) = 2

To refactor this into forementioned stored procedure you need to add a table-typed variable, and use a little bit of dynamic sql - because SQL does not have anything like arrays. Something like this:

CREATE PROCEDURE GetMoviesByGenres
 @genre_keys nvarchar(2000)
AS
BEGIN
 DECLARE @genre_keys_table table(genre_key int)
 DECLARE @genre_count int
 
 INSERT INTO @genre_keys_table
   EXEC(N'SELECT DISTINCT genre_key FROM T_GENRES WHERE genre_key IN (' + @genre_keys + N')')
 
 SELECT @genre_count = COUNT(*) FROM @genre_keys_table
 
 SELECT
  T_MOVIES.movie_key,
  T_MOVIES.movie_name
 FROM
  T_MOVIES INNER JOIN
  T_MOVIE_GENRES
  ON T_MOVIES.movie_key = T_MOVIE_GENRES.movie_key
 WHERE
  T_MOVIE_GENRES.genre_key IN (
   SELECT genre_key FROM @genre_keys_table
  )
 GROUP BY
  T_MOVIES.movie_key,
  T_MOVIES.movie_name
 HAVING
  COUNT(*) = @genre_count
END

If it wasn't clear from the code; @genre_keys takes a comma-delimited list of keys. That leaves an obvious injection vulnerability, so I would advise to have your calling code take an array of int, and not a string.
So that pretty much concludes that. If any of you ever end up as an intern at Tabeoka, you can now impress me with your mad SQL skillz.

Menno




* "him" because we've only ever gotten male interns. I'm prety sure I could get in trouble for poking and prodding a girl intern anyway. Both with the law, and my wife.

Monday, December 17, 2012

Html and Svg: handling events to and fro

I've been working on a website where I embed a couple of svg's in an html page. Actually, I embed the same svg in three places on one page. The svg in question has some script-driven animation, so I needed to use an object tag, rather than a simple img.
First challenge was this: I needed to trigger the svg animation for all svg's one after the other, which meant I had to call into the svg's script:

        function bounceBall(ball) {
            var svgView = getSvgView(ball);
            
            if(svgView)
                svgView.startBounce();
        }

        function getSvgView(ball) {
            var svgDoc;
            try {
                if (ball.getSVGDocument)
                    svgDoc = ball.getSVGDocument();
                else if (ball.contentDocument)
                    svgDoc = ball.contentDocument;

                if (svgDoc) {
                    return svgDoc.defaultView;
                }
            } catch (e) { }
            return null;
        }

When I initially call this function, the SVG dom might not be loaded yet. That's why I include the try/catch, and return null if an error occurs. Elsewhere in the code I set a setTimeout to retry 200 milliseconds later. The onload event is not quite reliable enough.

Next up was the click handler. If you simply add an onclick to the object tag, nothing happens when you click the svg. That makes perfect sense: the onclick is registered and handled within the svg, and never makes it to the html dom. I needed to have a click on the image open a little div in html though. From svg I could call the html javascript functions using top.someFunctionName(). I had the same svg image three times though, and it needed to do something different each time. Here's what I came up with:

Html:

<object type="image/svg+xml" data="/Content/Images/ball.svg" class="ball" style="left: 130px; top: 160px;" onclick="showPopup('homepopup2');"></object>

"But wait!" you say, "You just told me that doesn't work!". And it doesn't, but it would be pretty convenient if it did:

Html dom javascript:

        function setClickEvent(ball) {
            if (ball.onclick) {
                var svgwin = getSvgView(ball);
                if (svgwin) {
                    svgwin.eventHandler = ball.onclick;
                } else {
                    // if the svg view is not available,
                    // try again in 200 ms.
                    window.setTimeout(function() {
                        setClickEvent(ball);
                    }, 200);
                }
            }
        }

There you go. On load I simply funnel the onclick handler into the svg dom. The svg implementation is trivial:

    var eventHandler = null;

    function handleClick(){
      if(eventHandler)
        eventHandler();
    }


<circle cx="15" cy="15" r="5" id="ball" onclick="handleClick();" />

If you need this sort of thing more often - or for more events - you could work out a neat wrapper with  registerEventHandler(eventName, eventHandler) and triggerEvent(eventName) methods to reuse (and a html-side script that automatically hooks it up). I don't currently foresee a need for it myself though.

Menno

Tuesday, December 4, 2012

Anything but restful

Last week I was asked to integrate some "webservices" into a .NET application. I say "webservices", but that word can mean anything from SOAP to custom format XML to some icky CSV that uses the asterisk for a delimiter.
I was lucky though: the url made obvious that this webservice was WCF-based, some methods returning json, and equivalent methods returning xml. All request parameters are to be sent as json through the querystring.
I'm an optimistic fool, so I simply use the "Add Service Reference" to add a link to the service, and all seems well. Until I try to actually use the service: my application throws up the following:

Could not find default endpoint element that references contract 'IServiceInterface' in the ServiceModel client configuration section. This might be because no configuration file was found for your application, or because no endpoint element matching this contract could be found in the client element. 

Sure enough, when I check in my configuration file, the following has been helpfully added:

<configuration></configuration>

Well thank you very much, Visual Studio. You're a great help.
Google turns out to be more of a help, and points me to the following article telling me: what you're trying to do does not work and will not work. Because they're so RESTful. Instead I should be using the WebChannelFactory class to generate a channel and use that to call the webservice.
No problem.
I  re-use the proxy classes generated in my non-working service reference (but delete the wrapper classes), and point the WebChannelFactory to the generated service interface. Does that work now?
No of course it doesn't work: "405 http method POST is not supported by this url".
Sure enough, Fiddler shows that the service is being called using a POST of the request paremeter serialized as xml. "Stupid boy, " Google tells me again, "you should be adding the WebGet attribute to your method, and if you want json, you need to add a behavior to your endpoint that selects the JsonQueryStringConverter". "And while you're on it, " Google continues, "don't forget to define a UriTemplate for your WebGet attribute".
Done, done and done.
Now does it work? No of course it bloody well doesn't work. No more errors, but no deserialized data either. The json serialized data appears to be wrapped in a single key 'd' for all requests. The class structure doesn't match up to the json hierarchy, so nothing gets deserialized. So I wrap all my return types in a small generic class:

  public class JsonWrapper<T>
    private T _d;
    public T d {
      get { return _d; }
      set { _d = value; }
    }
  }

Finally I start seeing data. WCF and the one side, WCF on the other side and nothing works by itself. Some of the articles I was reading had the gall to tell me this was because WCF has great extensibility. Is "extensible" newspeak for "does nothing useful out of the box"?
Sure, it is very extensible, but in the time it took me to figure out how to get it to call a simple json webservice, I could just as easily have used the WebClient class to call the url, and run the return data  through  NewtonSoft's Json.NET. In fact, I could have done it three times.
If the service reference is able to properly generate proxy classes, why can't the service reference also send the necessary metadata to configure all that stuff I had to do manually? Where was the added value in all that WCF stuff? Is this a useful abstraction, or needless obfuscation?
Now that I've got a bit more of a handle on how it works, I'll give it another chance. But I'm not sold.

Menno

Monday, November 26, 2012

SVG is such a tease

A couple of days ago I was asked to look into animations that would work on iPad. You could use CSS3 tranformations, but I was excited to see what I could do in SVG instead. Why? Because why not!
Off I went, and not too much longer I had this: http://www.tabeoka.be/downloads/svg/blokskes.svg . Cute. Works smoothly on all browsers that matter. Is a little jittery on Opera.
Turns out SVG is a lot of things I've wanted HTML to be in the past. Have you ever created a DIV just to make a rectangle? SVG is for you. It's HTML for making pretty pictures. It supports css and most of the javascript DOM methods you're used to. Pick it up and go.
Back to my image though: I could slap an image on there, and pretend the website is being swallowed by a maelstrom. Right?
Well, here's a unicorn with an unfortunate case of being torn into rectangles:  http://www.tabeoka.be/downloads/svg/blokskes_fill.svg . The most unfortunate part though, is that the unicorn is being torn up very slowly. Unfortunate for the unicorn, certainly, but more unfortunate for my ambition to animate stuff using SVG. What's up with that?

I must be doing something wrong. I can't believe my computer can render this, but not chop up a unicorn (where are its priorities?). Internet Explorer 9 is supposed to have hardware accelerated svg rendering. If this is the result, it must have needed that acceleration real bad. And I can believe Microsoft messed up SVG performance in IE, but every damn browser is slow!
In the past I did some animation where I would suspend rendering while updating the object hierarchy, and then restart rendering. But this article suggests browsers are not stupid; that's too bad. I think I am to conclude that fully SVG-driven animations are not quite ready from prime time. But when the performance catches up, the object model will be ready. I like SVG, but it's such a tease.

Menno

Monday, November 19, 2012

Drupal: open-source CMS

Drupal has been pretty popular with the various Belgian governments. Any new websites created for a government agency are supposed to use an open-source CMS. Drupal's popularity (and its Belgian roots?) have made it the perfect candidate. Heck, even the king uses it. A new initiative is Drupal-as-a-service: pick your features and click "Create website". Off you go!
With the government's zeal to convert everything to open-source the buzz has been increasing. Universities request websites built on Drupal, marketing people want their new website in "Druple".

So what's up with this love for open source? I will now wield my razor-sharp intelligence to shamelessly make up what I think is most likely:

  • Avoiding vendor lock-in
    Every few years, the government is required to field a project to get price quotes from a number of parties, and then pick the best price quote.
    If a project has been written using a proprietary framework/platform/language/etc the best candidate will likely be the candidate who initially set up the project. Any other candidate would need to either swallow the costs of a steep learning curve, or be more expensive.
    Not so for open source. Anyone who knows Drupal/Joomla/Wordpress/But mostly Drupal can pick up a website and go! Money savings galore!
  • Open data
    Whether you have access to the source of your CMS or not, the data on your site is yours. If you switch to a different system, you want to keep your data. If a proprietary system perishes, your data could perish with it. In an open source system, you have the ultimate data spec: the source code.
  • Security updates
    Whenever a security leak is found, noble developers will flock to it, and release a security patch in no time at all. Government sites need to be secure, right?
  • Oh! The modules!
    If you have a Drupal-based website and you want to add a online shop, you only need to install Drupal commerce. Works instantly! Hardly any configuration required! Money savings galore!
    More to the government point: integrate with the Belgian electronic ID card (currently has some security issues).
  • Open source means no license means cheap! Right?
    No it doesn't. And I doubt the government is stupid enough to believe this.
Some of those are pretty solid reasons. I want the government to spend my tax money wisely (frugally even), and store my personal data on secure servers! Who wouldn't?

But here's the thing: when we make a Drupal website, the customer comes back and tells us

"We don't like the way this editing form works. Can you make it do x and y instead?"

And we can. The customer's request makes sense: core Drupal is pretty spartan, and a lot of modules are a tad confusing. We just code up a nice custom module that does exactly what the customer wants. 
But here's the catch:
Those custom modules can be neither open-source, nor secure (nor very well-written for that matter).
That includes some modules that I've written. It's vendor lock-in all over again. 
We inherited a Drupal project from a competitor, and the last few weeks I've been poring over custom modules that implement some form of url rewriting using taxonomy terms. It's a very neatly commented and indented mess, and has a fair number of bugs - I'm not sure I can do better. I'm familiar enough with Drupal, but my employer has had to swallow these costs anyway. You can't pick up a major website and run with it. Open source doesn't matter that much here.

As far as the open data is concerned, I think that's a valid point. I have written a proprietary CMS in .NET, and I encrypt all website data using AES-256 before storing it in the database using an 'optimized' version of Base64. I double-dare customers to switch to a competitor (I kid, of course). But I could do such a thing, call it 'Enterprise-level security', and sell it to the banking industry.
Using open source, getting my data is not necessarily easier, but I know it can be done.

Lastly, about the security updates. The sysadmin is usually the weak link here. Nobody will likely ever find a security hole in my proprietary CMS, because nobody cares. There will, 100% sure, be security updates for Drupal. For all eternity: either you patch or you're vulnerable. My CMS may actually be safer than Drupal. Not by virtue of its technical qualities, but just because it's a tiny fish in a pretty small pond.
After all: wasn't Apple repeatedly the first to be hacked at pwn2own ? 

Menno

Monday, October 22, 2012

SSMS: OutOfMemoryException executing a large SQL batch

So you're executing some beast of an Sql batch using the Management Studio, for instance the result of "Generate Scripts" on another database. Then all of a sudden you get a OutOfMemoryException. Even when just keeping the entire script in memory, poor SSMS is hanging on by its fingernails. How could you expect it to also execute that file, and give you the results?

Thankfully there is a command-line Sql server client Microsoft thoughtfully provides together with Sql server. If you're not able to import a large sql file using SSMS, navigate to the Binn folder of your Sql server folder (C:\Program Files\Microsoft SQL Server\100\Tools\Binn here) in Command Prompt, and type the following:

osql -S databaseserver -U username -P password -d DemoDatabase -i c:\demo.sql

That executes the file C:\demo.sql on databaseserver in the context of DemoDatabase using the login data provided. This will scroll a bunch of query results in your command prompt window. If you'd rather examine these results in detail later, the -o parameter writes this info to an output file:

osql -S databaseserver -U username -P password -d DemoDatabase -i c:\demo.sql -o c:\output.txt

That should work, even when SSMS chokes on the sheer size of your query file.

Monday, October 15, 2012

text-transform: uppercase subtleties

So last week I received an interesting question from a customer. He complained that in Chrome on Mac, the category 'Soßen und Dips' ("Sauces and dips") on the german (obviously) version was rendered as 'SOSSEN UND DIPS' (wrong), rather than 'SOßEN UND DIPS' (right). Notice that ß and SS are semantically identical - a latin1 collated database will consider those strings to be identical.
On Internet Explorer, the ß was displayed fine.
It didn't take long to figure out that the menu item had text-transform: uppercase applied, and that this caused the transform of ß to SS. What's more, Safari and Firefox also displayed SS instead of ß. My Google search led me to page https://bugzilla.mozilla.org/show_bug.cgi?id=354451 . This page indicated that transforming ß to SS was deliberate, and not a bug at all. Der Spiegel suggests that ß should, in capitals, always become SS.
So now I only need to convince the customer that their browser can spell their language better than they can.

Menno




As an interesting aside: a basic test case to check browser behavior sees Internet Explorer 9 also rendering SS, not ß. Changing the document mode down to IE7 shows ß again. The actual online page is in IE9 mode, and does not have a X-UA-Compatibility meta tag. The question then becomes, why does it show ß? No idea yet.

Thursday, October 4, 2012

In which I learn about multithreading performance

... or an exercise in optimizing IndexOf on List<T> for multicore.

So I had a great plan.
.NET 4 introduced AsParallel() into LINQ (well, 'PLINQ' , but try using that word in conversation without giggling uncontrollably). So how about re-implementing some of these methods in a multithreaded way for .NET 3.5?
To get my feet wet, I decided to start off simple: I re-implement IndexOf on List<T>. Should be easy:

  • Perfect for splitting up, each thread just takes a range of the list
  • No need for critical sections
So I wrote an extension method IndexOfParallel<T>:
  • Creates as many threads as there are logical cores,
  • pass them a list range, and a status object
  • each thread checks its range of the list, sets the status object to found and returns
  • main thread calls .Join() on each created thread
Done! Let's check how much better it performs compared to the regular IndexOf!

Looking for a thousand random ints in a list of a million ints:
  • Regular version: 8565064 ticks
  • Multithreaded version: 542255931 ticks
Whoops! Only sixty times slower!

Perhaps a million ints is too small to have the proper effect. Let's try ten million:
  • Regular version: 9131999 ticks
  • Multithreaded version: 149267210 ticks
Well, that's only sixteen times slower now. Progress!
I check the source for IndexOf on List<T>, which uses Array.IndexOf on its internal array. Turns out it uses a native method for basic types. Clearly I can't improve on that. Perhaps I should compare against a List<string> (100,000 items):
  • Regular version: 7044903 ticks
  • Multithreaded version: 93284309 ticks
Thirteen times slower. This is starting to piss me off. Why is it slow? What is slow?
Perhaps I shouldn't be trying to reinvent the wheel. What happens if I just use the overload of IndexOf on List<T> that takes a range instead of writing my own loop? Clearly I'll be losing my early exit, but with enough cores maybe it evens out:
  • Regular version: 7563221 ticks
  • Multithreaded version: 140339244 ticks
Nope! Twenty times slower! If I fire this version off against a List<int> of a million, I gave up waiting for it to finish at all. Extremely slow. I suspect the native method lock the List's internal array in memory, and that may be marked as a critical section.
Whatever the reason, let's scrap this, and go back to my own loop. What if we unroll the loop, say, four times? If that speeds it up significantly, we can deduce the loop implementation is slowing everything down:
  • Regular version: 7122743 ticks
  • Multithreaded version: 89569552 ticks
A small gain: twelve times slower. Clearly the loop is fine. So the thread creating is probably to blame. Let's not create our own threads, and use the ThreadPool:
  • Regular version: 7034966ticks
  • Multithreaded version: 5879994 ticks
Whaaa! Success! It's not much, but I finally beat the built-in version. Let's see if we can improve it a bit more. How about turn the status class into a struct, and avoid the getter for the properties by turning them into public fields? Obviously we need to ref the method parameter:
  • Regular version: 6979197 ticks
  • Multithreaded version: 4006500 ticks
Awesome! If we increase the number of strings in the list to a million, the effect increases too:
  • Regular version: 76802790 ticks
  • Multithreaded version: 36655462 ticks
Twice as fast! I'm sure this can still be improved significantly. I still need to figure out at what list size it makes sense to switch to multithreaded. If you're working on a List<T> where T's implementation of Equals is slow, it should do better. There are a number of lessons learned already though:
  • This method's only worth it in a few situations. Mostly just not.
  • Only create new Threads if you will hold onto them for a long time. Creating new threads takes long. 
  • Prefer using the ThreadPool.
  • Measure Measure Measure!
It'll be interesting to see how we manage reimplementing .Where(). The Predicate delegate could be pretty expensive. IEnumerable<T> is forward only. Will exporting to List<T> and splitting up be faster? Excitement!

So there we are.We beat the built-in IndexOf.

Menno


Here's, for now, the final result:

using System;
using System.Collections.Generic;
using System.Threading;

namespace Tabeoka.Extensions
{
    public static class ExtensionMethods
    {
        public static int IndexOfParallel<T>(this List<T> source, T item)
        {
            int threadCount = GetOptimalThreadCount(source.Count);

            if (threadCount == 1)
                return source.IndexOf(item);

            SearchStatus status = new SearchStatus()
            {
                Found = false,
                FoundIndex = -1
            };

            // Looks like the ThreadPool always hangs onto at least 
            // # of cores threads, if left unset otherwise
            using (ManualResetEvent resetEvent = new ManualResetEvent(false))
            {
                int threadsFinished = 0;
                for (int i = 0; i < threadCount; i++)
                {
                    int fromIndex = (source.Count * i) / threadCount;
                    int toIndex = (source.Count * (i + 1)) / threadCount;

                    ThreadPool.QueueUserWorkItem(new WaitCallback(delegate(object t)
                    {
                        SearchListRange(source, item, fromIndex, toIndex, ref status);
                        if (Interlocked.Increment(ref threadsFinished) == threadCount)
                            resetEvent.Set();

                    }));
                }

                resetEvent.WaitOne();
            }

            return status.FoundIndex;
        }

        private static int GetOptimalThreadCount(int listCount)
        {
            // needs more sophisticated logic
            return Math.Min(listCount, Environment.ProcessorCount);
        }

        private static void SearchListRange<T>(List<T> source, T item, int fromIndex, int toIndex, ref SearchStatus status)
        {
            int i;

            for (i = fromIndex; i < toIndex; i += 4)
            {
                if (source[i].Equals(item))
                {
                    status.FoundIndex = i;
                    status.Found = true;
                    return;
                }

                if (source[i + 1].Equals(item))
                {
                    status.FoundIndex = i + 1;
                    status.Found = true;
                    return;
                }

                if (source[i + 2].Equals(item))
                {
                    status.FoundIndex = i + 2;
                    status.Found = true;
                    return;
                }

                if (source[i + 3].Equals(item))
                {
                    status.FoundIndex = i + 3;
                    status.Found = true;
                    return;
                }

                // if some other thread found it; quit searching!
                if (status.Found)
                    return;
            }

            // finishing up loop
            for (i = i - 3; i < toIndex; i++)
            {
                if (source[i].Equals(item))
                {
                    status.FoundIndex = i;
                    status.Found = true;
                    return;
                }
            }
        }
    }

    internal struct SearchStatus
    {
        public bool Found;
        public int FoundIndex;
    }
}

Thursday, September 27, 2012

Complaining about Drupal

Kindly allow me to bitch some more about Drupal. I'm a bit frustrated.
  • Array parameters: just about every function in Drupal takes an associative array:
    array(
          'field_name' => 'publication_datum',
          'cardinality' => 1,
          'type'        => 'datetime',
          'settings'    => array (
            'granularity' => array (
              'month' => 'month',
              'day' => 'day',
              'year' => 'year',
              'hour' => 0,
              'second' => 0,
              'minute' => 0,
            ),
          )
        )
    

    This effectively defeats any auto-complete you might have had in your php editor. Of course I see why they did it; it makes everything 'neat', and it certainly is flexible. Except now you're not only unclear about what you should pass into a parameter, you don't even know the parameters. Add-on modules could look for any key, and there's no way to find out, except by proper documentation (which is rare) or poring over the source code.
    Distinct advantage for the lazy coder: if you need to send an extra variable, you can just hitchhike along with any array that's headed in the right direction if you make sure the key isn't taken.
  • Template naming: do you want to override the rendering of a particular element? You could hook into a theme process function and mess around with the render array or whatever, but the easier solution is actually to give a template file a cryptic name with lots of dashes. This file name functions somewhat as a css selector: the more specific ones override the more general ones. Thankfully there's a module to help you pick a template name: Theme developer offers a plethora of  possible template names for each part of your page. That's pretty handy, but also indicates I'm not the only one who has trouble keeping track.
  • The hooks! Oh, the hooks! There are hundreds of them, and you can go ahead and create your own if the fancy strikes you. Hooks takes different numbers of parameters, of different types (and with or without &), and there is no way to find out without, once again, checking the documentation or the source code.
    I know, PHP does not have strong typing, but the small amount of meta data that would otherwise be available is eradicated by kinda sorta duck typing that's going on in Drupal. Again: I can see why they did it, and it is even clever. But it's still frustrating.
The basic problem it comes down to is this: a lack of discoverability of features. When I'm developing a Drupal module I will have dozens of tabs open in my browser, looking for a clue how to use a particular module. Open source is good; it allows me to figure out what's wrong, even if I did not write the code. But just providing the source code is no replacement for proper documentation and sample code. It's just lazy.

Menno

Wednesday, September 5, 2012

Drupal 7 and Asp.NET webforms

I've been manhandled into writing some modules for Drupal lately. Weeping and gnashing of teeth abounds.
Php is not exactly my favorite language to begin with, and Drupal is extensive and complex and wholly alien to me.
One thing has struck me though, working through the Drupal hooks madness: just how much some of it resembles Asp.NET webforms. A recurrent criticism of Asp.NET has been its confusing event pipeline, and how WebControl abstractions give less control over the generated html.
But lo and behold: Drupal 7's "render array":

$form['taal'] = array(
    '#type' => 'radios',
    '#options' => array(
      'nl' => 'Nederlands (NL)',
      'en' => 'English (EN)',
    ),
    '#required' => FALSE,
    );

This generates a list of <input type"radio">. Change type to 'select', and it generates a <select>. It's also possible to pass simple html string into a render array, like a LiteralControl. The point is to be able to change properties about generated content from other modules, without having to do lots of string parsing.
And then I read in my "Building Drupal Modules" book about how you can hook into the rendering process to change things. Here's the list of available functions:

  • template_preprocess()
  • template_preprocess_[NAME OF HOOK]()
  • [NAME OF MODULE]_preprocess()
  • [NAME OF MODULE]_preprocess_ [NAME OF HOOK]()
  • [NAME OF THEME]_preprocess()
  • [NAME OF THEME]_preprocess_ [NAME OF HOOK]()
  • template_process()
  • template_process_ [NAME OF HOOK]()
  • ... you know, forget it
Total of twelve, for one possible hook, and there will be lots of hooks - add six for each. This is also an event pipeline of sorts. It's just that event handlers can only be added by AutoEventWireup, and it's for everything, not just page events.

Mind you, I'm not criticizing Drupal. Whenever you aim to provide a flexible web platform, you will come up with solutions that have to be either complex, or not enough.

Still, pain.

Menno

Tuesday, September 4, 2012

About those animated ajax page loads in MVC ...

A little while ago I showed a way to chain animation functions with callbacks in javascript. That was part of a web site in MVC the requirements of which were as follows:

  • It needs to use awesometastic animation prettiful swooping panel dynamified load superlicious "Html5" etc.
  • It needs to do well in search engines, and
  • work reasonably well in IE7
The animations were part of the ajax-loading of the page content, but -of course- people needed to be able to link to any page directly as well.

So here's what I did:

  • I created a ViewConfig class. This class contains the current configuration of the browser screen: what menus are shown, which background(s) are showing, etc etc:
        public class ViewConfig
        {
            [JsonConverter(typeof(StringEnumConverter))]
            public MenuDisplay Menu
            {
                get { return _showMenu; }
                set { _showMenu = value; }
            }
    
            [JsonConverter(typeof(StringEnumConverter))]
            public BackgroundsDisplay Backgrounds
            {
                get { return _backgrounds; }
                set { _backgrounds = value; }
            }
    
            public string Root
            {
                get { return _root; }
                set { _root = value; }
            }
    ...
    
  • I created a BaseModel class that includes a ViewConfig property (and my menu data and other data shared among all models):
        public abstract class BaseModel
        {
            public List<Business.MenuItem> MainMenuItems
            {
                get { return _mainMenuItems; }
                set { _mainMenuItems = value; }
            }
    
            public ViewConfig ViewConfig
            {
                get { return _viewConfig; }
                set { _viewConfig = value; }
            }
    
            [JsonIgnore]
            public string ViewConfigJson
            {
                get { return  _viewConfigJson; }
                set { _viewConfigJson = value; }
            }
    ...
    
  • Each controller takes a boolean json parameter that determines if the Model will be sent to the view, or rather simply returned as a JsonActionResult:
        public class InhoudController : BaseController
        {
            public ActionResult Index(string taal, string inhoudId, string json)
            {
                bool returnJson = "true".Equals(json);
                Models.InhoudModel model = new Tabeoka.Epsilon.Web.Models.InhoudModel();
    
    ...
    
                if (returnJson)
                {
                    var jsonResult = new JsonNetResult();
    
                    jsonResult.SerializerSettings.ReferenceLoopHandling = Newtonsoft.Json.ReferenceLoopHandling.Ignore;
                    jsonResult.SerializerSettings.MaxDepth = 1;
                    jsonResult.Data = model;
    
                    Response.Expires = 0;
                    Response.CacheControl = "no-cache";
    
                    return jsonResult;
                }
                else
                {
                    model.ViewConfigJson = model.ViewConfig.ToJson();
                    return View(model);
                }
    
  • In the pages I then simply send an ajax request, get my model as json, and move, step by step, from my current ViewConfig to the new ViewConfig, using supertastic fantalicious animations.
There are just two obvious drawbacks to this approach:

  1. As you can see, I need to send my ViewConfig twice; once as a string for the initial ViewConfig when a page is loaded through a View. The second when the entire model is serialized to json. It's ugly. I could serialize in my View to fix this.
  2. Worse: I have a bunch of html rendering code in javascript. Ideally I would be able to use the same template in javascript and .Net. I'm not sure how and if that could work though.
Search engines and javascriptless (or javascript-poor) clients, I can just present a static version of the site. Other browsers will automatically have links on the page 'ajaxified'.

Conceivably in the future I can take this approach, and improve it by POSTing my current ViewConfig in my ajax request, build the exact delta between that and the requested page, and only fill up my Model with data to the extent my ajax code needs it.

Menno

Thursday, August 16, 2012

And let me draw your attention to the left ...

I would like to take this opportunity to point everybody to this wonderful article: A truly lazy OrderBy in LINQ.
The default OrderBy's execution in LINQ only being somewhat deferred always irked me. This version is much better.

Menno