mercredi 31 juillet 2013

Replace STL Algorithm with "Parallel" Algorithm.

The goal is to keep a C++ syntax and STL style of writing code while using parallelism. It's a recent topic and lot of C++ Framework emerged in the 2 or 3 previous year.

 Note that an automatic replacement of all STL algorithm by a parallel equivalent isn't a good idea, so that in any case you will have to update your code.

in the following example, I just define a small lambda and apply that one on a 1d array using std::transform.
I called  a parallel version using the PPL(in the VS'2012). Only have 2 cores but seems lead to the expected factor 2.



#include <ppl.h>

void main ()
{
float otherScalingFactor = 0.3f;
#define size 59999999
float* local_arr = new float[size]; std::fill(local_arr, local_arr + size, 1.5f);
float* out = new float[size];
auto normalize = [&] (float x) { return fabs(x / otherScalingFactor) * otherScalingFactor + expf(x) * cosf(x) ; };
time_t start = time(NULL);
std::transform(local_arr, local_arr + size, out, normalize);
time_t end = time(NULL);
std::cout << "end in ..." << difftime(end, start) << std::endl;

std::fill(out, out + size, 0.0f);

start = time(NULL);
concurrency::parallel_transform(local_arr, local_arr + size, out, normalize);
end = time(NULL);
std::cout << "end in ..." << difftime(end, start) << std::endl;

delete [] local_arr;
delete [] out;

getchar();
}

mardi 30 juillet 2013

Producer - Consumer: a common conception error.

Producer-Consumer design or Pipeline of task are often use in programming to introduce multi-threading. But some programmer are wrong in the way they implement that. For example, I found the following question on Stackoverflow: concurrent_queue memory consumption exploded, then program crashed. The question is why the memory rise a limit so that the program crash !

After some comment, I finally post an answer, but I realize that it may be useful to explain a bit more with some schema.


If the producer run 2x faster than the consumer the number of element in the Fifo will grow linearly. So as in the real life, we have to specify a limited stock size. So that if the stock is full, the producer must wait.


That can be achieve with a dual synchronization:
  • Consumer wait if the fifo is empty and is awake if an element is pushed.
  • Producer wait if the fifo is full and is awake if an element is remove so that the size goes under the threshold.
For the code, see my answer on Stackoverflow!

dimanche 28 juillet 2013

Optimization - Where Meta-Programming can help...

In this post, I will show 2 different methods of computing the n-th element of the Fibonacci Suite.
The goal is to show that in some context instead of using run-time to compute something, you can compute that at compile-time.

  • run-time, is what you want to optimize.
  • compile-time, what you can increase (in some limit) without impact on your customer.
If compile-time become really too long, you will be depressed waiting in front of your computer. But your compiler can do a lot for you.

See below a simple recursive function to compute the n-th element of the Fibonacci suite.


int Fibonacci_recursive(int nieme)
{
if( 0 == nieme)
return 0;
if( 1 == nieme)
return 1;

return Fibonacci_recursive(nieme-1) + Fibonacci_recursive(nieme - 2);
}


Now if you use that function "Somewhere in your code", and disassemble the resulting binary, you will see something like:

00E91357 call Fibonacci_recursive (0E91270h)

The code you call use a lot of op-code and call itself several time depending of the element you ask. This kind of computation is not time-constant !

So it will be interesting if compiler can compute the value! At run-time we will have directly have the value in constant-time.... To achieve that goal, you can use Macro (Preprocesor), or Template (C++ Meta Programming). I choose the template way :


template<int I> struct Fibonacci_meta {
enum { value = Fibonacci_meta<I-1>::value + Fibonacci_meta<I-2>::value };
};
template<> struct Fibonacci_meta<1> {
enum { value = 1 };
};
template<> struct Fibonacci_meta<0> {
enum { value = 0 };
};


And now if you write Fibonacci_meta<10>::value in your code, and analyze the result, you will just see something like:

008F7BFF push 37h

And as you may know 0x37 == 55... the 10-th element of Fibonacci.
It's a simple example, but we removed several function call and have let the compiler find the result at compile-time!!!!


vendredi 26 juillet 2013

Playing with JS and Web API.

One thing really fun is this area, is that more and more data are freely available from/to the Web. Those data can be REALLY free like Weather Real-time information like the service i used below, or NEED APP REGISTRATION.

Note that for a lot of Web API, App Registration is free, it's more for tracking and avoid duplicate App development or that an IP 'get' too much data.

I'm not a Web Developer, but I think that as a developer if you don't know basis of JavaScript and HTML in our 21 century, you would be lost. So my today experiment, I will get Temperature information for my city, and simply display that.

So in the code below I declared 2 HTML label using an ID, temp_celsius, and temp_fraenheit.


<div>
<p> Rennes Today's Temperatures</p>
<ul>
<li><text> Celsius : </text><label id="temp_celsius" ></label></li>
<li><text> Farenheit : </text><label id="temp_farenheit" ></label></li>
<ul>
</div>


The result is here

Rennes Today's Temperatures
  • Celsius :
  • Farenheit :

To feel those 2 HTML label with data, i started using JQUERY (you can live without, but when you become familiar with its notation to access DOM element, you always start with it):


<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.5.1/jquery.min.js"></script>




And now let's call the OpenWeather service . It propose a free Web/REST API to get (or push if you setup your own Weather station) data using JSON format.
My request is "http://api.openweathermap.org/data/2.5/weather?q=Rennes,fr" and in response i received something like:

{"coord":{"lon":-1.67429,"lat":48.11198},"sys":{"country":"FR","sunrise":1374813353,"sunset":1374868234},"weather":[{"id":802,"main":"Clouds","description":"scattered clouds","icon":"03d"}],"base":"gdps stations","main":{"temp":297.15,"pressure":1012,"humidity":50,"temp_min":297.15,"temp_max":297.15},"wind":{"speed":2.6,"deg":290,"var_beg":250,"var_end":330},"clouds":{"all":36},"dt":1374849000,"id":2983990,"name":"Rennes","cod":200}


One of the advantage of using JQuery is that you can get and parse the JSON data in only 1 call of $.getJSON. The field Temp is express in JKelvin as you can have guess when looking its value (297.15 ...).


<script type="text/javascript">
$(document).ready(function(){
var json_request = $.getJSON("http://api.openweathermap.org/data/2.5/weather?q=Rennes,fr&callback=?", function(data) {
console.log("in cb ????" + data.main.temp);
var celsius = (data.main.temp - 273.15);
$("#temp_celsius").html(celsius);
var farenheit = (celsius * 1.8 ) + 32
$("#temp_farenheit").html(farenheit);


}).done(function() { console.log( "second success" ); })
.fail(function() { console.log( "error" ); });
});
</script>


There is nothing really dynamic after that, but my next step will be nicer, it will be the "Stackoverflow Question Meter" to dynamically show how many question are ask on Stackoverflow and using Google Chart API.

samedi 20 juillet 2013

Counting occurence and histogram

A recurrent question on Stackoverflow [c++] is, hopw can we count word, sentence in string or a text file, or how can we build an histogram showing all unique number in a list and their number of occurence.

In fact every time those question found quite the same answer because in all case, whatever you want count, it can be really easy to do with C++ and STL. If we use the std::map class we can do that in 2 loop.

First, imagine we have a list containing random number.


srand(time(NULL));
std::vector list;
int N = 1 , M = 100;

for (int i = 0; i < M; ++i) { int rnd = M + rand() / (RAND_MAX / (N - M + 1) + 1); list.push_back(rnd); }


Ok, so now we have 100 number with some redundancy, let's count that with a map.


std::map histo;

for (auto rnd : list)
{
histo[rnd] += 1;
}


And it's done !, nothing else .... Just a loop to display the result:


for(auto var = begin(histo) ; var != end(histo) ; ++var)
{
std::cout << var->first << " have " << var->second << " occurence " << std::endl; }


Simple and efficient

Why you really need a "Gravatar" !

At first glance when a web site asked me for a gravatar, I found that annoying and just let my account without avatar or picture of me.

But few week ago I changed my mind, Having a gravatar account let you change your picture once and all the account you linked with, will be automatically update!

At the end, it's just the same thing under Google .... 1 Profile picture for everything, for all the account you have.

So if you want a Gravatar it take only few minutes.

I use mine for Stackoverflow, CoderBits and some other and finally I found that more convenient than uploading a picture for each!

lundi 1 juillet 2013

Don't forget to 'EncodeURL'

In  http://tinyurl.com/qa3nmtv I presented a small script/exe I made to quickly convert selected path (folder or file) from Explorer to a string in the clipboardwhich can be 'paste' in a browser editor as an URL to a local resssource.

In fact I forgot something important in my script. You may hate or love it but Windows allow 'spaces' in path. So I have to convert SPACE to %20, to build a correct URL.

I updated my script this morning:

https://github.com/alexbuisson/Project/tree/master/UsefullScript

Just pull Path2URL.exe, and configure your StExBar like in the following Snapshot.





Visual Studio 2008Randomly crashing.


If you are using VS'08 and a lot of plugin you may experience some random crash when using "Intellisense" functionality (performing a right click in the source code) or when switching from Debug to Release configuration.

 I may be really difficult  for some to figure from where and for why the crash/freeze occur.

In fact I meet that issue and I finally attached another Visual Studio instance with a debugger and realize that VS was hanging somewhere in the FEACP.DLL

That DLL is the engine of Intellisense.

If you have that kind of problem and that you want double check or experiment VS'08 without Intellisense running behind, you just have to rename that dll in your VS'08 setup folder and restart VS.

It's work fine but without Intellisense, you really need additional plugin to provide, some source browsing capabilities ("Find all references", etc...)


Build a script/tool to make your life easier.

Hi,
Just wanted to share some work done to simplify the everyday life of my teammates.

One week ago, one of my colleague had a lot of file path to share through our CRM system and in fact he found that was very boring because he had to copy all network path and apply a transformation on every string. To transform network file or folder path from their UNC or Drive path (mounted drive) representation to a file/folder URL style that can be use to access local system storage through a browser.

To do that he had to 'manually' switch all '\' (windows path separator) to '/' and concatenate 'file://'. I understood it could become a pain to do that kind of boring task, so I developed a simple script/executable to do that for one or multiple selected file or folder with only 1 click from Windows Explorer.

My Teammates and I already used StExBar to improve our Windows Explorer experience. It's a highly customizable tools in which you can add your own custom command, with button and/or hot-key.


As the function we need has only to run under windows, I choose a windows only tool called AutoHotKey to build a script performing multiple path selection, conversion to URL style and injection into the clipboard.

AutoHotKey provide every things I needed to develop the script:
  • File parsing 
    • StExBar selection (single or multiple) are store in a temp text file that can be pass to any cmd or application through "%selafile"
  • Clipboard
    • From AHK (AutoHotKey) point of view the winows clipboard is just a variable.
  • String parsing, Regex Matching etc...
    • To detect Drive letter
    • To detect UNC Path
    • To replace '\' and concatenate the 'file://' prefix.


link := "file:///"
pathrep := ""

CR := Chr(13)
LF := Chr(10)

GetUNCPath(letter)
{
  localName = %letter%
  length := 1000
  VarSetCapacity(remoteName, length)
  result := DllCall("Mpr\WNetGetConnection"
      , "Str", localName
      , "Str", remoteName
      , "UInt *", length)
  if (ErrorLevel <> 0 || result != 0)
  {
     return ""
  }
  else
  {
;     MsgBox, %remoteName% (%length%) -- result: %result%
    return remotename ; end function
  }
}

Loop Read, %1%
{
 p := A_LoopReadLine
 ;MsgBox %p%
  if ( RegExMatch( p , "[A-Za-z][:]") ) ; match a regex for drive letter "^:"
  {
    unc := GetUNCPath( SubStr( p, 1, 2) )
    if ( unc <> "" )
    {
      withoutDriveLetter := SubStr( p, 3, strLen(p)-2 )
      pathrep = %link%%unc%%withoutDriveLetter%%CR%%LF%%pathrep%
    }
  }
  else ; should already be an unc (check to be sure)
  {
    if ( RegExMatch( p , "\\\\") ) 
    {
      pathrep = %link%%p%%CR%%LF%%pathrep%
    }
    else
    {
      ; Msgbox "ignored " %p%
    }
  }
   
}

StringReplace, pathrep, pathrep, \, /, All
; MsgBox %pathrep% 
clipboard =  %pathrep% 

The main advantage of using AHK script is that it can be build and provide as a binary file without any dependency. And the integration of the resulting executable as an StExBar Command is really simple like you can see in the following snapshot:


That script is publicly available on my GitHub repo