Mayur Deore's Blog

Post info:

Memoization: Optimizing ASP .NET by caching C# function

This article is about Optimizing ASP .NET server side execution using Memoization technique.Before understanding Memoization,let’s discuss the simple but time consuming scenario first.

Consider the simple example in ASP .NET Web-form, I want to create Table control populated with list of students and bind that control to asp:panel. The reason to consider this example is it’s really simple but time consuming when data to be populated is increased. Obviously we can populate gridview which in-turn will be rendered as table, but to demonstrate the memoization I’m going to populate data manually.

Normally we will create Table WebControl and add TableRow WebControl for each student.

First we want simple student entity class,which is as follows.

    public class Student
    {
        public string name { get; set; }
        public string description { get; set;}
    }

Then some method to get TableRow let’s say dataToRow, which is wrapped in HTMLtable class as follows.

public class HTMLtable
{
    TableRow tr;
    TableCell td1;
    TableCell td2;
    public TableRow dataToRow(Student stud)
    {
        tr = new TableRow();

        td1 = new TableCell();
        td1.Text = stud.name;
        tr.Cells.Add(td1);
        td2 = new TableCell();
        td2.Text = stud.description;
            
        tr.Cells.Add(td2);
        
        return tr;
    }
}

As you can see dataToRow accepts single student object and returns TableRow with name and description of that student in different TableCell.

As this article is only to demonstrate Momoization, I’m going to create student object list by dumping 10000 of same data.Following function returns that list of student objects.

private List getStudent()
{
    var studentList = new List();

    var student = new Student();
    for (int i = 0; i < 10000; i++)
    {
        student.name = "student";
        student.description = "description";
        studentList.Add(student);
    }
    return studentList;
}

I have added Label on aspx page to display the time consumption result.And code-behind is as follows.

protected void Page_Load(object sender, EventArgs e)
{
    var stopwatch = new Stopwatch();
    var rowList = new List();

    var htmlTable = new HTMLtable();
    var studentList = getStudent();
    
            
        stopwatch.Reset();
        stopwatch.Start();



        foreach (var stud in studentList)
        {
            rowList.Add(htmlTable.dataToRow(stud));
        }



        stopwatch.Stop();

    
    lblResult.Text = "Ticks: " + stopwatch.ElapsedTicks + " ns: " + 
     ((double)stopwatch.Elapsed.TotalMilliseconds * 1000000).ToString();
}

After running the result on webpage is as follows.

normal

(NOTE: The result varies on each refresh but average time is 10-17 ms)

Some of you may argue that it’s quite fast as operation is done within 20 ms, so what’s need of optimizing this method. It may look negligible problem now but considering the big enterprise software or Web Application,where billions of data is to be processed this problem may look much bigger.

In above example, dataToRow is called for each record of student with same data, But even the same data is passed to method, it processes same operation each time and gives same result each time.

To optimize this type of operations we need to cache the functions, so when next time the function is called with parameter value it will return the result cached instead of recalculating or repeating the operations to get the result, This is called Memoization.

Memoization is technique to cache the function result and return result from cache if same request is made.

NOTE: I recommend to cache the function which are to much complex and time consuming and may be called by passing same parameters.

Let’s consider our example, now to use memoization create generic method which will accept the function.This generic method will check the dictionary for match, if found then the result will be returned without executing the passed function else the passed function will be executed and the result will be stored in dictionary before returning result.

public static class utility
{

    public static Func<param, returnValue> memoize<param, returnValue>(
        this Func<param, returnValue> _function
        )
    {
        var memoryList = new Dictionary<param, returnValue>();

        return (prm) =>
        {
            returnValue returnData;

            if (!memoryList.TryGetValue(prm, out returnData))
            {
                returnData = _function(prm);
                memoryList.Add(prm, returnData);
            }

            return returnData;
        };

    }

}

As above function is generic, it will memoize any function having one parameter one and one return value. But for now let’s utilize above construction to optimize the dataToRow function and analyse the difference between normal processing technique and memoization technique.

protected void Page_Load(object sender, EventArgs e)
{
        var stopwatch = new Stopwatch();
        var rowList = new List();

        var htmlTable = new HTMLtable();
        var studentList = getStudent();

        var str = new StringBuilder();

        var NormalTime = 0.00;// Normal Operation Time in nanosecond
        var OptimizedTime = 0.00;//Optimized Operation Time in nanosecond

        /* Iterating 5 times to get multiple set of result for analysis*/
        for (int i = 0; i < 5; i++)
        {

            #region normalOperation  

            stopwatch.Reset();
            stopwatch.Start();



            foreach (var stud in studentList)
            {
                /* Normal call to dataToRow */
                rowList.Add(htmlTable.dataToRow(stud));
            }



            stopwatch.Stop();

            NormalTime += stopwatch.Elapsed.TotalMilliseconds * 1000000;


            /* Don't concate string using "+" use StringBuilder for better performance*/
            str.Append("NORMAL:
"+
            " Time: " + ((double)stopwatch.Elapsed.TotalMilliseconds * 1000000).ToString()
            + " ns
");//ignore use of "+" for concate


            #endregion

            #region memoizeOperation

            /*Initialize memoize method by 
            * passing func<> i.e dataToRow*/
            var memoryFunction = utility.memoize<Student, TableRow>(htmlTable.dataToRow);
            // NOTE: dataToRow is yet executed it's just passed as parameter

            stopwatch.Reset();
            stopwatch.Start();

            foreach (var stud in studentList)
            {
                /* This may call the dataToRow 
                    * if match not found 
                    * else return cached result */
                rowList.Add(memoryFunction(stud));
            }


            stopwatch.Stop();

                OptimizedTime += stopwatch.Elapsed.TotalMilliseconds * 1000000;

            /* Don't concate string using "+" use StringBuilder for better performance*/
            str.Append("Memoize:
"+
                " Time: " + ((double)stopwatch.Elapsed.TotalMilliseconds * 1000000).ToString()
                + " ns

);//ignore use of "+" for concate


        }

            str.Append("NORMAL Average Time         :"+ NormalTime/5 +" ns ");
            str.Append("
MEMOIZE Average Time    :" + OptimizedTime / 5+" ns");
            str.Append("
Ratio percentage        :"+NormalTime/OptimizedTime*100+" %");
            #endregion
            lblResult.Text = str.ToString();

}

Above I have processed the normal method and memoized method 5 times to multiple set of results to compare. And also calculated average times and ratio percentage at last. The result is as follows.

optimized

As you can see the optimized method is almost 10 time faster than optimized one, Interesting thing here is that the addition of all 5 optimized execution time is much less than lowest of all normal execution time.

I refreshed the page number of times and the ratio percentage never came down to even 700%. The reason is in normal execution the function executed each time, and in memoize technique the function only executed first time for above data.

Obviously, this exact scenario will never occurred in real Web Application development where same data will be processed thousand time in same way. But still using this technique in certain cases it will optimize the process not 1000% or 8000% but 150-200% increase in performance can be definitely achieved.

If I have missed something or something wrong found please let me know, This will help to increase my knowledge.

Thanks for reading, If you have suggestions/queries comment below. Share this article to friend.

Mayur Deore

Facebook Twitter LinkedIn 

Leave a Reply

Your email address will not be published. Required fields are marked *