A colleague of mine hit a strange bug today. It so happened that we use a bastardized dependency injection method that takes into account the WCF session before returning an implementation of an interface. In a piece of code the injection failed and we couldn't see why for a while. Let me give you a simplified version:

var someManager=Package.Get<IManager>();
var someDTOs=Cache.GetDatabaseObjects().Select(x=>x.Pack());

public class DataObject {
    public string Data {get;set;}
    public DataObjectDTO Pack() {
        var anotherManager=Package.Get<IAnother>();
        return new DataObjectDTO {
           Data=anotherManager.Process(Data)
        };
    }
}

Package.Get will attempt to find a session object and if not it will use another mechanism, but if it finds one, it will only use it if it is not expired or invalid, else throwing an exception. This code failed in the Pack method, when trying to get an instance of IAnother. Please take a few moments to reflect on why (and no, it's not that between calls the session expired).

Show explanation

OK, what is going on here? First Package.Get works, then it doesn't. The method GetDatabaseObjects returns some objects that were previously stored in memory. Explanation: the objects were created by another thread. That means that a method of those objects will be executed on that thread, which contains whatever Session another user used.

It is such an insidious bug that we had to think a few minutes to figure it out. And the solutions are not perfect:

• Load all objects in cache from the service loader, rather than lazy, so that they are all instantiated in a thread with no WCF context
• Put a try/catch block around the code that validates the session and treat invalid sessions as null
• Create a helper class that holds the Pack functionality and keep data objects methodless

Obviously all of these might work, but they all have ugly side effects. Personally, I am inclined to recommend the third solution. First of all it respects the separation of concerns of classes, but second of all the helper class can be used as an extension method class, so the usage would be exactly the same.

Now that is interesting, isn't it? A clear difference between instance methods and extension methods is the execution context, something that I had not been consciously aware of before. obj.Pack() translates to DataObjectsExtensions.Pack(obj) which is run on the calling thread. I am now wondering if the web of extensions methods in ASP.Net Core has something to do with this.

I've stumbled upon a very funny exception today. Basically I was creating a constant string from adding some other constant strings to each other. And it worked. The moment I added an integer, though, I got The expression being assigned to 'Program.x2' must be constant. The code that generated this error is simple:

const string x2 = "string" + 2;

Note that

const string x2 = "string" + "2";

is perfectly valid. Got the same result when using VS2010 and VS2015, so it's not a compiler bug, it's intended behavior.

So, what's going on? Well, my code transforms behind the scenes into

const string x2 = "string" + 2.ToString();

which is not constant because of ToString!

The only way to solve it was to declare the numeric constant as string as well.

This clause is so obscure that I couldn't even find the Microsoft reference page for it for a few minutes, so no wonder I didn't know about it. Introduced in SQL Server 2005, the TABLESAMPLE clause limits the number of rows returned from a table in the FROM clause to a sample number or PERCENT of rows.

Usage:

TABLESAMPLE (sample_number [ PERCENT | ROWS ] ) [ REPEATABLE (repeat_seed) ]

REPEATABLE is used to set the seed of the random number generator so one can get the same result if running the query again.

It sounds great at the beginning, until you start seeing the limitations:

• it cannot be applied to derived tables, tables from linked servers, and tables derived from table-valued functions, rowset functions, or OPENXML
• the number of rows returned is approximate. 10 ROWS doesn't necessarily return 10 records. In fact, the functionality underneath transforms 10 into a percentage, first
• a join of two tables is likely to return a match for each row in both tables; however, if TABLESAMPLE is specified for either of the two tables, some rows returned from the unsampled table are unlikely to have a matching row in the sampled table.
• it isn't even that random!

Funny enough, even the reference page recommends a different way of getting a random sample of rows from a table:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Even if probably not really usable, at least I've learned something new about SQL.

Update:
More about getting random samples from a table here, where it explains why ORDER BY NEWID() is not the way to do it and gives hints of what really happens in the background when we invoke TABLESAMPLE.
Another interesting article on the subject, focused more on the statistical probability, can be found here, where it also shows how TABLESAMPLE's cluster sampling may fail in spectacular ways.

.Net Core Web API uses Newtonsoft's Json.NET to do JSON serialization and for other cases where you wanted to control Json.NET options you would do something like

JsonConvert.DefaultSettings = (() =>
{
    var settings = new JsonSerializerSettings();
    // do something with settings
    return settings;
});

, but in this case it doesn't work. The way to do it is to use the fluent interface method and hook yourself in the ConfigureServices(IServiceCollection services) method, after the call to .AddMvc(), like this:

services
    .AddMvc()
    .AddJsonOptions(options =>
    {
        var settings=options.SerializerSettings;
        // do something with settings
    });

In my particular case I wanted to serialize enums as strings, not as integers. To do that, you need to use the StringEnumConverter class. For example if you wanted to serialize the Gender property of a person as a string you could have defined the entity like this:

public class Person
{
    public string Name { get; set; }
    [JsonConverter(typeof(StringEnumConverter))]
    public GenderEnum Gender { get; set; }
}

In order to do this globally, add the converter to the settings converter list:

services
    .AddMvc()
    .AddJsonOptions(options =>
    {
        options.SerializerSettings.Converters.Add(new StringEnumConverter {
            CamelCaseText = true
        });
    });

Note that in this case, I also instructed the converter to use camel case. The result of the serialization ends up as:

{"name":"James Carpenter","age":51,"gender":"male"}

I was doing this silly HackerRank algorithm challenge and I got the solution correctly, but it would always time out on test 7. I wracked my brain on all sorts of different ideas but to no avail. I was ready to throw in the towel and check out other people solutions, only they were all in C++ and seemed pretty similar to my own. And then I've made a code change and the test passed. I had replaced LINQ's OrderBy with Array.Sort.

Intrigued, I started investigating. The idea was creating a sorted integer array from a space delimited string of values. I had used Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).OrderBy(v=>v); and it consumed above 7% of the total CPU of the test. Now I was using var arr=Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray(); Array.Sort(arr); and the CPU usage for that piece of the code was 1.5%. So it was almost five times slower. How do the two implementations differ?

Array.Sort should be simple: an in place quicksort, the best general solution for this sort (heh heh heh) of problem. How about Enumerable.OrderBy? It returns an OrderedEnumerable which internally uses a Buffer<T> to get all the values in a container, then uses an EnumerableSorter to ... quicksort the values. Hmm...

Let's get back to Array.Sort. It's not as straightforward as it seems. First of all it "tries" a SZSort. If it works, fine, return that. This is an external native code implementation of QuickSort on several native value types. (More on that here) Then it goes to a SorterObjectArray that chooses, based on framework target, to use either an IntrospectiveSort or a DepthLimitedQuickSort. Even the implementation of this DepthLimitedQuickSort is much, much more complex than the quicksort used by OrderBy. IntrospectiveSort seems to be the one preferred for the future and is also heavily optimized, but less complex and easier to understand, perhaps. It uses quicksort, heapsort and insertionsort together.

Now, before you go all "OrderBy sucks!", read more about it. This StackOverflow list of answers seems to indicate that in case of strings, at least, the performance is similar. A lot of other interesting things there, as well. OrderBy uses a "stable" QuickSort, meaning that two items that are compared as equal will appear in their original order. Array.Sort does not guarantee that.

Anyway, the performance difference in my particular case seems to come from the native code implementation of the sort for integers, rather than algorithmic improvements, although I don't have the time right now to grab the various implementations and test them properly. However, just from the way the code reads, I would bet the IntrospectiveSort will compare favorably to the simple Quicksort implementation used in OrderBy.

I've met an interesting case today when we needed to manipulate data from tens of thousands of people daily. Assuming we would use table rows for the information, then we get a table in which rows are constantly added, updated and deleted. The issue is with the space allocated in table pages.

SQL works like this: If it needs space it allocates some as a "page" which can contain more records. When you delete records the space is not reclaimed, it remains as is (this is called ghosting). The exception is when all records in a page are deleted, in which case the page is reused as an empty page. When you update a record with more data then it held before (like when you have a variable length column), the page is split, with the rest of the records on the page moved to a new page.

In a heap table (no clustered index) the space inside pages is reused for new records or for updated records that don't fit in their allocated space, however if you use a clustered index, like a primary key, the space is not reused, since there needs to be a correlation between the value of the column and its position in the page. And here lies the problem. You may end up with a lot of pages with very few records in them. A typical page is 8 kilobytes, so a table with a few integers in a record can hold hundreds of records on a single page.

Fragmentation can be within a page, as described above, also called internal, but also external, between pages, when the recycled pages are used for data that is out of order. To get a large swathe of records the disk might be worked hard in order to jump from page to page to get what is logically a continuous blob of data. It is disk input/output that kills a database.

OK, back to our case. A possible solution was to store all the data for a user in a "blob", a VARBINARY column. For reads or changes only the disk space occupied by the blob would be changed, with C# code handling everything. It's what is called trading CPU for IO, which is generally good. However this NoSql-like idea itself smelled badly to me. We are supposed to trust our databases, not work against them. The solution I chose is monitoring index fragmentation and occasionally issuing clustered index rebuilding or reorganizing. I am willing to bet that reading/writing the data equivalent to several pages of table is going to be more expensive than selecting the changes I want to make. Also, rebuilding the index will end up storing all the data per user in the same space anyway.

However, this case made me think. Here is a situation in which the solution might have been (and it was in a similar case implemented by someone else) to micromanage the way the database works. It made me question using a clustered index/primary key on a table.

These articles helped me understand more:

• SQL Server Heaps, and Their Fragmentation
• Effective Clustered Indexes
• Defragmenting Indexes in SQL Server
• When a Delete isn’t Really a Delete…

I had this problem with Perforce where I accidentally Reconciled my offline work with all the files in /bin and /obj folders, resulting in a huge 6000+ file changelist. OK, simple one button mistake, surely there must be some one button undoing what I just did. It appears there is not.

In order to fix this I have to follow these steps:

1. Change the settings of Perforce to show files even in changelists larger than 1000 items (the default value)
2. Select by hand in the changelist window the files from obj and bin folders and using Revert on them
3. Revert the few other files that were unwanted in the changelist, like .suo and .user files - note that Revert on added files doesn't delete them, it just unadds them
4. Create a file with paths to ignore and then use p4 set P4IGNORE=<filename> for future reconcile work

What didn't work was adding a filename or path filter when visualizing the changelist, since that is a changelist filter, not a files filter. It will show you changelists that have files that contain the pattern, but not filter the files inside the changelists themselves.

For reference, the p4ignore file I used looked like this:

p4ignore
bin/Debug
obj/Debug
*.suo
*.user

Note that I also added the p4ignore file itself, although the file was not in any Perforce repository (yet).

"But, Siderite, you should use Git (or whatever source control is the newest fad at the moment)!" Wish that could, my friend, wish that I could.

Update May 2020: I used this on a web site and the body was white. It may be that the bug in Chrome was solved in the meantime.

Update October 2019: a CSS media feature (prefers-color-scheme) can be used in conjunction with this. A recent development, it's a media query that allows a browser to activate CSS code based on the theme set in the operating system. You set your preference in Windows or MacOS or wherever and then sites that use prefers-color-scheme will take advantage of that. Something like this:

@media (prefers-color-scheme: dark) {
  html,img, video, object, [style*=url] {
    -webkit-filter:invert(100%) !important;
    filter:invert(100%) !important;
  }

  /* this was solving a bug in Chrome that seems to have been fixed
  body {
    background:black;
  }
  */
}

  I am a very light sensitive person. Shine a light in my eyes and you limit my productivity immensely. Not to mention it makes me irritable. Therefore I often have the desire to turn cheerful black on white sites to a dark theme, where the colors are reversed. I am sure other people have the same problem so I thought of building a browser extension to enable a switching button between the two.

  The first problem is that I need to interrogate all the elements in a page, including the ones that will be created later. The second is that even so I would have problems determining the dominant color of images. But there is something I can use which makes all of this unnecessary: using the invert CSS filter! Since I already use a browser extension that injects my own styles in any site - it's called Stylish and I highly recommend it - all I have to do is apply a filter on the entire site, right?

  Wrong! The problem is that when you invert an entire site, all images on the site get inverted, too. That also includes videos and Flash objects. The worst offenders here are the elements that sport a background image that is declared via CSS, since you can't create a CSS selector for them. I am going to present my partial solution and maybe you can help me find a more elegant or more complete one. Here is a general dark theme stylesheet, without the elements that have a background image declared via CSS (it does include those with a background image declared inline, though):

 html,img, video, object, [style*=url] {
    -webkit-filter:invert(100%) !important;
    filter:invert(100%) !important;
  }

 /* this was solving a bug in Chrome that seems to have been fixed
 body {
   background:black;
 }
 */

  What it does is invert the entire page (html), then reinvert video, img, and object elements, as well as those with "url" in the style attribute. In Chrome, at least, there seems to be a bug in the sense that the backgrounds of the direct child elements are not inverted, which means body, as the first child, needs to have the background set to black specifically. (this seems to have been solved by May 2020) The hack to invert elements with "url" in style is pretty ugly, too.

  What I think of a solution is this:

• inject Javascript to enumerate all elements present and future using document.createTreeWalker and Mutation Observers, check if they have a background image and if so, add a class to them
• inject the CSS above with an additional rule for the class for the elements with background image

  However, this doesn't completely solve the problem. One of the major issues is the inverted colors sometimes look dumb. For example a red background turns cyan, white text on light gray background turns black text on dark gray background, which makes it hard to read. I've tried various other filters, like hue-rotate or contrast, but it doesn't really help. Detecting individual color patterns doesn't really work, as the filter attribute affects an element and all of its children. The CSS above only works because the images are inverted again when the entire page has been inverted.

  The good news is that most of the time you may use the CSS above as a template, then add various rules (manually) to fix small issues with colors of backgrounds. Even if I don't package this in an extension, you have the power to create your own themes for various sites. Never again will you be subjects to the tyranny of the happy bright shiny people!

I was glad to attend the 565th SQLSaturday in Bucharest yesterday and, while all presentations were cool, I wanted to share with you some specific points that I found very revealing. Without further ado, here is the list:

• SQL execution plans are read from right to left - such a simple thing, but I remember when I was trying to read them from left to right and I didn't get anything. In SQL Server Management 2016 you also get a "live" version, which shows you an execution plan while it's executing. Really useful to see where the blocking operations are.
• Manually control your statistics update - execution plans are calculated based on statistics, but the condition for updating the statistics is to have changes in a number of 20% of the rows plus 500 of any table. This default setting is completely arbitrary and may cause a lot of pain. Not only updating the statistics blocks your table (which means more chances that the table will be locked when it is most used), but sometimes the statistics are not useful. One example are reports which may receive a startdate/enddate range or a count or something like that which makes the number of rows affected vary immensely with different parameters. Use OPTION(RECOMPILE) for that.
• Look for a difference between estimated and actual rows in a query plan, which leads to tempdb spills, which leads to unwanted IO operations - before a query, an execution plan is created or reused, based on statistics, as I was saying above. Once a plan has been chosen, though, it doesn't change during its execution. Basically what this means is that the structure of the plan remains unchanged between the estimated and actual plan. Also based on the plan, memory is requested and never changed. So if the plan asks for 10KB of memory and you need 1000KB, the rest of 990 will be stored and used from tempdb even if there is enough memory to put them in, since the memory requirements don't change from estimated to actual. The reverse is not much better, since a plan may ask for a lot of memory when it only needs little, thus making everything else on that machine have less available resources.
• SQL default settings suck - there was an entire presentation about that, it is useful to think a little about it. So many settings are legacy things that make no sense, like the initial database size, the autogrow size, index fill factors, maxdop (degree of parallelism), parallelism threshold, used memory (ironically, using all of it may be hurtful as it takes it away from other processes which leads to using the swap file), etc.
• Look for hard page faults - this counter is much useful than the soft page faults, which are fixable faults. A hard page fault is indicative of unnecessary IO operations, which are orders of magnitude slower than memory use.

There are a lot more things that I want to explore now, since I participated to the event. You may find the files for the presentations in the same place as the full list of talks at SQLSaturday.

After a slightly misused sabbatical year, I went through a period of trying to get hired. That means interview after interview with people that were assessing my fit within their company. Man, that sucked! I mean, I am a white male professional in a business where everyone is looking for personnel and still it was frustrating, demeaning and painful. But I am not here to complain (maybe a little :) ), only to share my experience and my... constructive criticism.

The story

OK, so first off, the only other real experience in looking for work was more than ten years ago and then I was an absolute beginner on the market. However, back then I knew I was a nobody, while now I know that my experience and passion put me way up there as usefulness and value go. I may have started off this campaign with an unhealthy level of smugness, but it goes off quickly, I assure you.

I am lucky that I had this year of experimenting before I started looking, which allowed me to treat it as any other experiment: I accepted almost all interviews and I went diligently through the entire process, no matter my personal opinion about the company. That helped a lot as a learning experience; while I know how to code, it quickly became apparent that I have no idea how to convince others about it. I set up to try everything, learn from it, while continuing to be principled. In my mind that meant completely honest. I didn't expect company people to be honest with me, but that was on them. I would be a perfect WYSIWYG candidate. Better to fail fast, rather than have a miserable experience in the relationship. BTW, that is also my strategy with girls, which explains why I am virgin. I stuck to my guns, though.

The experience

I am not going to name names here. This is not about how awful some companies may have been. It is all about my perception of the hiring process. And it is that it sucks!

I don't know if in other fields it goes smoother, but imagine this: the only people that have any idea about how to hire people are the HR people and they have no idea what software programming is like. I could be married with an HR manager and she still would not know anything about software development. The technical people may know how to code, but they have no idea how to determine if the other person is any good and if you are a technical person you are definitely not an human resources person. I applaud people who can be both, mostly because I have not met one and I can't think of any scenario that would produce such an individual other than some radioactive alien arthropod biting a regular person.

Funny enough, compared with my past, is that HR mostly liked me while the technical people (the majority more than a decade younger) mostly dismissed me. At first I felt like a complete impostor (of course), my self esteem plummeted (which didn't help any), and I was about to beg for a job (which is what most people do, I hear). However, I tried to see the situation from the point of view of the people trying to hire me (I know: shocking!) and I could understand their situation and empathize. Think about it. How would you test someone for a programming job? Who would you call in that meeting? What would be the salary that you would budget for that person (in EUR, after taxes)?

Did you really think about it? Come on, make an effort. I guarantee it's worth it.

OK, so the HR people looked at my resumé and saw that I have had a lot of stable jobs before in all kinds of environments. I was a pleasant enough person (I mean, for a techie, which means without obvious homicidal tendencies) with a very good understanding of the English language. No obvious conflicts, although I may have been too honest in my (err.. constructive!) criticism of past employment. I mean, come on!, every dev can tell you that managers don't know what they're doing, right? If I think about it, the job of the HR department seems fairly simple to me: look for a candidate that fits the profile, lure them in, do the most simplistic psychological screening possible, then pass it along to the tech department. It's something that AIs will probably take over soon. I may fondly look backwards to these times, when there existed people that were actually biased towards me! The typical HR person is a girl. Now, if I am being insensitive here, I apologize, but if you want to seduce a tech to the point where he would do anything to come to you, you use a nice, sexy girl. It's only natural when devs are mostly male virgins. To be honest, these girls could have hated me or wanted me to have sex with them and I would have had no clue whatsoever. If they said it, I took it for granted. If they lied, again, it's on them. If they remained quiet, then I couldn't parse it into text and who's fault is that?

So then there was the tech interview. You have some guy who thinks he's God because he can code and maybe have some overview that is slightly larger than those of his juniors. He is young, probably coming from some technical university (yes, in Romania people actually do look for coding work after studying Computer Science). He has no idea how he needs to conduct an interview, but admitting to that, even to himself, is a bit too discordant with his view of his person. So he does what every tech would do in this situation: he Googles it. You might be amazed, but Google actually turns up some good advice, but you must be willing to admit that your expectations for how to do that may have been completely wrong. So he does the second thing anyone does when Googling: looks for links that validate their own beliefs (and also have some template for interviews that they can quickly print and use).

Am I being unfair here? Probably. But it is a good theory to explain the types of interviews that I had and how they all seemed carbon copied after each other. The template is basically this:

1. an algorithmic question, such as: how do you refresh a sorted list from another complete sorted list, or how do you intersect two sorted lists, or how do you search into a sorted list or... wait a minute, are they all about bloody sorted lists?
2. general algorithmic knowledge questions, such as: what is the difference between a list and a linked list, or an array and a list, what are the complexities of operations on lists. Pretty much there has to be a data container there.
3. general language knowledge questions, such as: behavior of some implementation in a specific language, the results of SQL queries, characteristics of SQL indexes, some HTML stuff, the life cycle of ASP.Net if you are really lucky...
4. tools and ways of working in tech from previous employers. Here they are actually interested, because while they appear to be judging everything you say, they actually want to hear of better ways of working themselves.
5. questions about a project you really liked or had a lot of influence over. Yeah! And while you feel like an idiot because no one ever let you work on a project that you think was special, the interviewer learns from your experience and adapts it to their crappy project.
6. asking you if you have questions for them and looking like they expect you to have some really sensible and relevant questions when all you want is to know if they want to have you or not

The existence of the first step is being fed by sites like HackerRank, Codility and CodingGame, which should never be considered as anything else than learning tools, if not just silly games. However, since these people went through grueling university lectures about algorithms and then inflated their own ego playing on the web sites above they assume you should know about them too. It doesn't matter that they rarely found use of any of it when working on their projects, they just push it under the vague concept of "wanting to see how you think". However, they are not logical problems (like they used to put 5 years ago, copying from Google and the like), they are very specific coding situations. You may know the exact solution - because you played around with algorithms when bored - or you might have no idea how to solve the problem.

And here you are now, facing a guy that looks critically at you, while trying to think of the problem, finding the best solution and doing it before the guy gets bored. It will take him about 60 seconds to get bored, too, as he already knows the answer to the question and he feels it's obvious and the only one possible. Hell, he knew how to solve this before he even left university! It doesn't matter that several scenarios fight for supremacy in your head, that for each there is another solution, that the very simple solution feels too simple and your brain is wracking itself to find another one - that would be probably either wrong, over engineered or both. And you want, you really want to implement a three step algorithm that you know always works (1. Google it 2. Think of something better 3. Use the best implementation found), but you believe it would be perceived as not knowing your stuff. I mean, what if you are at work and your Internet dies? Surely you need to solve the problem anyway, right?

In truth, the lucky scenario is if they send you to HackerRank or something similar to solve a technical test before you meet with anybody. That goes over fast and easy, while you hack comfortably in your underwear and you have no stress about who is thinking what. The unlucky scenario is that you get a guy who thinks you are not a true developer unless you are working on open source projects on GitHub in your spare time. Oh, and they need to be interesting to him.

Yet, after you go through the first two steps, the rest are a breeze: you know your stuff, you know your languages, you can even think of a project or two that had something remotely instructive in them. It feels like you went over a bump, but now you can go full speed. They ask you various things about your past experience, you gladly oblige, make a few jokes, get some laughter, start to feel good about yourself. Surely, you will pass the interview.

And then you get "the call", where you know you have failed from the tone of the HR girl who needs to tell you that they won't be going further with it. You still hope against hope while she goes on and on and on through her complex script of letting you go easy. She thinks she's being thoughtful, yet you are a tech and you want the answer first and the explanations after. And you despair. Obviously, you suck. You will never get a job. You are worthless, less than worthless, a complete buffoon. And here you were, thinking that years of successful work with people that appreciated your efforts meant anything. When was the last time you learned something new anyway? Last month? Three programming languages and five new frameworks launched since then, not to count the new versions of old frameworks that you never got around to master. Who were you kidding? There are ten year olds that can code better than you. And they are not married yet! You know getting a dog will ruin your career. You are a fossil, admit it! In five years you will be begging for food on the street with a sign that says "Will code for bread". And you know what? You are right: you are an idiot!

I cannot claim absolute truth here, because I don't have enough data to arrive at a clear conclusion. That is because when they flunk you, the sweet HR girl stops contacting you altogether. If you are lucky the company didn't use their own human resources and instead you arrived through a dedicated HR firm (headhunters) and they have the decency to not only tell you didn't pass, but also make the effort to tell you why. The people you maybe knew at that company and were really supportive of you joining their team drop from the face of the Earth. Clearly, you were too stupid to work there, so they cut you off. At the very best you are an emotional mess and they don't want to have anything to do with that. So the next section is mostly speculation, but I will try to make it sound good.

The Explanation

There are a zillion reasons people don't want you in their team on the specific project they are working on and that have nothing to do with your value as a human being.

You might have asked for a sum that is too large for what they were prepared to offer. Even if you are that valuable, they are too cheap for it. It's like the girl who dumps you without telling you why (maybe mumbling something about you being insensitive) because you said you liked anal and she was afraid to try it. It may also be because you think you deserve more than people are actually willing to pay in general. That's on you. However, the correlation between your skills and your pay is not linear. It mostly depends on the market. After all, you are trying to sell yourself. You are already a whore, now you are just negotiating on the price. Today you may be a hero, tomorrow you will be the guy that made some money in that [enter fleeting fad] boom and lost it all in the subsequent crash.

People might put a lot of value on algorithms. It may be a good decision, because in their project they often meet situations where good algorithmic knowledge saves the day. If you are not good at it, or you couldn't prove it in the makeshift interview you flunked, they have every right to not go through with it. They might also not know any other way to test your knowledge and be too lazy to actually look for value in people. There a lot of other similar reasons that you may file under this scenario. They wanted something specific from you, didn't tell you and you don't have it.

They think you are old. And you may just well be. Age discrimination aside, why should they hire someone like you when they perceive the same value from a guy 20 years younger - and way cheaper? If I had to chose, I would have no qualms whatsoever. This is also linked to expectations. Remember when you were counseled to try to move to a manager position before you got to [enter ridiculously low number here]? That translates to the expectation that after that age, being a simple techie means there is something wrong with you. This will never ever change. Look at the age average in all the big companies: it's about 30. Startups even less, around 22. That doesn't mean you need to become a manager, I am sure old managers feel just as threatened. Plus, you might really suck as a manager. I know I would. Unofficial sources say that even the places that usually hire people for experience (like government jobs) stop looking at resumes for people over 45. Age does matter, so plan for it.

And then there is the idea that if you are inexperienced you can learn quicker the things that "you really need", like that framework that became famous while you were reading this blog post. You may be experienced, but will they need to fight with you on whether to use ASP.Net MVC over ASP.Net forms? (or is ASP.Net MVC obsolete already? I don't know, I was blogging). I don't know if that's true. I did learn quicker when I was young, but that was mostly by failing miserably again and again. On the other hand a job position where you are hired for your ability to fail your tasks sounds pretty good, doesn't it?

There is also the personal thing. You might have rubbed someone the wrong way. That means not that you are an awful person, but that you just don't match with a person who you might have had to work with if they went forward and hired you. Again, want to be married with the girl that hates you, no matter how big her boobs are? You may be an asshole, but maybe the other person was, too. Some people might feel threatened by you, either because you threatened their life if they don't hire you or because they think you are way sexier than them and you would cock block their attempts to woo the HR girl. You won't become a better person by trying to be liked by everyone. They might have hated your shirt, for example, the one that you thought would look really professional, but they saw as threatening, because they usually work in shorts and t-shirts. Point is, they had some expectations and you didn't meet them. Were they justified? You don't know and you shouldn't care.

The position you would be working on is equally important. You might be a brilliant web developer, but if they actually wanted a server guy, or viceversa, they will drop you. They will not admit that they were not specific in their job description, of course, and instead just blame you for not being "a good fit". Imagine you are a cube that is crying it didn't fit in a circular hole. Ridiculous, right? I mean, would the tears be blocky? As a specific example: I went somewhere for several interviews. I was "a perfect match" for one and not the right person for another. The JD document they sent for both positions was identical.

Solutions

Since I code and have an overview on life, I can definitely tell you how interviews should be conducted, but you will have to buy the paid version of this blog for that. See, I am learning fast, in one phrase I was both a tech, a business person and an asshole.

The truth is that the only way I could think of that wasn't insulting to everyone's intelligence was to actually show them a computer, a real problem, and let them fix it with me watching and helping next to them. And it still wouldn't be sufficient. If it were "real" enough, then it would take time to understand all of the aspects of the problem. The guy might be overly nervous with me next to him. I know people that can only work when no one is watching, and they do great work. Plus, they may have experience on that exact problem and suck at anything else.

Unfortunately, in all my interviews the only tools that I had to work with were pen and paper. Putting aside the fact that I don't even understand my own writing, the last time I had to actually write anything on paper was... oh yeah, the last time I was looking for a job. Does it make sense to conduct software development interviews with no computer? I would say no.

Conclusions

There is a schism between what they expect and what you expect, what you think of yourself and what they do. That is the real reason behind every failed interview. It doesn't really matter if they had unrealistic expectations, but it matters a lot if you had. Like every experiment: acquire data, reason about the data, propose a theory that explains it, test it against new data. The best way to achieve anything is to change your behavior towards the goal. The important thing here is to define the goal. Is it to get hired at any and all costs? Or is it to find the place where you will enjoy working, keep growing and be appreciated for your efforts?

In the end it so happens that not only did I get hired at the company I was aiming for, but I did it on the position I feel I was best suited for, rather than some mediocre second best. Like with dating girls, it is worth waiting for the right one. And with software, you get to do side projects, too!

Update 12 August 2018: I've updates the project to Core 2.1 and changed the Add method to treat OutOfMemoryExceptions in case of memory fragmentation.

I have been looking for a job lately and so I've run into these obnoxious interviews when someone asks you to find the optimal algorithm for some task. And as much as I hate those questions in an interview, they got me thinking about all kinds of normal situations where the implementation is not optimal. I believe it will be hard to find something less optimal than the List<T> implementation in .Net.

Reference

For reference, look at the implementation code in its entirety.

Story

I will be discussing some of the glaring issues with the code, but before that, let's talk about the "business case". You have a C-like programming language, armed with all the default types for such, like bool, int, array, etc. and you need a dynamically sized container, one where you can add, insert and remove elements. The first idea is to use an array, then resize it accordingly. Only you can't know how large the array will need to be and you can't just allocate memory and then resize that allocation, as other variables have already occupied the next blocks of memory. The solution might be to allocate an initial array, then - when its size is no longer sufficient - create a larger one, copy what you need and make the changes in it.

A comment in the source tells us what the developers meant to do: The list is initially empty and has a capacity of zero. Upon adding the first element to the list the capacity is increased to 16, and then increased in multiples of two as required. So, an empty list is just a wrapper for an empty array. A list with one element occupies the size of a 16 element array, but if you add up to 17 elements, the array will double and continue to double.

Implementation

Let's check the algorithmic complexity for the add operation. For the first 16 elements you just add elements in the internal array, n operations for n elements. Once you get to 17, the complexity increases, as you need to copy all previous 16 values first. Now it's 16+16+1, which continues up to 33, where you have 16+16+16+32+1. At 65 it's 16+16+16+32+32+64+1. So while we are adding element after element the operational complexity is on average twice as much as using an array. Meanwhile, the space occupied is half more than you actually need.

Insertion is similarly tricky, but even more inefficient. Basically, when you insert a value or a range, the first operation is EnsureCapacity, which may copy the entire array in a new array. Only afterward the insert algorithm is run and it again copies the part of the array found after the index for the insert.

Removal works in the opposite direction with the caveat that it never decreases the size of the array. If you added 10 million records in your list, then deleted them, your list now contains an internal array that is 10 million elements in size. There is a method called TrimExcess that tries to solve this, but you must call it manually. At least RemoveAll is using an O(n) algorithm instead of calling Remove repeatedly, which would have been a disaster.

The piece of code that sets the internal dimension of the list is actually in the setter of the Capacity property, and it dumbly creates an array and copies the values from the current one to the new one.

A lot of the other operations are implemented by calling the static methods on the Array class: Array.IndexOf, Array.Sort, Array.BinarySearch, Array.Reverse, etc.

The last issue that List has is that, as an array wrapper, it needs contiguous memory space. There will be times where your code will fail not because there is not enough free memory, but because it is fragmented and the runtime cannot find a free block that is large enough for your data.

Better solutions

Before I start spouting all kinds of stupid things, I will direct you to the venerable C5 collection library, which is very well designed, documented and tested. It contains all kinds of containers to optimize whichever scenario you might have been thinking about.

Let's think solutions now. The major problem of this implementation is the need of a continuous array. Why not solve it by adding more arrays instead of replacing the one with another twice as large? When the capacity is exceeded, we create a new array of similar size, then link it to our list. And since we want to have index access, not linked list access, we need to add this array into an array of arrays.

What would that mean? Memory doesn't need to be contiguous. Adding is twice as fast. Inserting is fast, also, as you only need to insert a new array between existing arrays and move around the data in a single inner array. Accessing by index is a bit more complicated, but not by much. Removal is just as simple, with the added bonus that some inner arrays might become empty and be removed directly.

This is by far not "the best" option, but just one level of optimization that tries to fix the biggest single problem with the current implementation. As one of my friends used to say: first collect data about your program, see where the bottlenecks are, then proceed to fix them in decreasing order of importance. The source can be found on GitHub.

Notes

A tester program of sorts is showing the Count, Capacity and time for random operations for a normal list and the FragmentList<T>. The next line shows the individual lengths of the inner arrays. Note that I cheated by using Lists instead of arrays. It only makes sense, as the simplistic operations of List<T> now have a limited negative impact on individual fragments. Take note of AutoDefragmentThreshold, which is 0.8 by default. It replaces all the internal lists with a single contiguous one when there are more than 80% of internal lists that are smaller than a tenth of the total count. To disable the feature you need to set the value to more than 1, not 0. I also implemented all the public methods of List<T>, although you might only need to implement IList<T> and the *Range methods.

Well, enjoy! Hope it helps.

Today I've learned something old. Yeah, it has been there from .NET 2.0 and probably at one time or another I knew about it, then I just forgot about it. I am talking about the string.Split method overload that accepts a StringSplitOptions enumeration. In fact, it is an enum just in name, because it has only two possible values: None and RemoveEmptyEntries.

I had forgotten that I can eliminate empty entries like that, even if, truth be said, string splitting with a regular expression and maybe then filtering the results with LInQ feels much better, both as readability and control over the result. So, what is your preferred method of splitting, say..., a sentence into words?

text.Split(" \t".ToCharArray(),StringSplitOptions.RemoveEmptyEntries);

or

Regex.Split(text,@"[ \t]+").Where(s=>!String.IsEmptyOrWhiteSpace(s));

? (I realize that in the case I am describing I don't need the LInQ at the end except in fringe cases, but it was an example)

No, it's not about mine, although this blog has had its ups and down. What I want to talk about is the list of blogs I am following and how it (d)evolved.

When I was an enthusiastic beginner in software development I was hunting for interesting blogs that would give me valuable insights into the minds of good developers, the quirks of frameworks, the hidden tools and processes that would make my life better. I was adding blog after blog to my RSS list. Later on, I kind of stopped. I had things to do, work to be done and unfortunately went through some jobs that were not conducive to learning. Perhaps seeing myself as an expert also hindered enthusiasm in learning (note to self: don't do that!). The obsolescence of the tool I was using to read RSS with and the death of Google Reader also did not help. So recently I just went back to that list of blogs and started organizing it with a new tool. I use Feedly now, in case you were wondering.

Today I had an epiphany. I have over 150 blogs that I am "following", 100 of which are software related, yet only very few of them are actually spewing content anymore. In my three year hiatus from blog reading most of the technical blogs just ... stopped. Some of them just plain vanished, complete with content that I had linked to in my own articles. At that time I was considering blogs as permanent as you can get. I mean people just write stuff for the heck of it, so others can read and learn. There would be no reason for any of this to disappear - there are still pages from 1990 active on the Internet, for crying out loud! So what happened?

One theory is that blogs were created as representations of a person's evolution. For example you are a good WPF programmer and you create something like Dr. WPF's blog. When you stop doing WPF (because Microsoft dropped the ball with it!) you stop writing. Perhaps the author still blogs in other places, other blogs that are thematic, I don't know. Another theory is that people just blog at a certain stage in their life; it's like a quarter-life crisis. When they mature, people stop blogging (which says something...). Maybe the social media explosion pushed people away from personalized platforms and they do all their publishing on Twitter, Facebook, LinkedIn, Medium and so on. As the IT industry moves at an ever increasing pace, the blogs may turn into antiquated relics that are obsolete by the time several posts have been published.

I feel sad either way. When I started blogging, people would come to me for help. After all I started the site years before StackOverflow arrived on the scene. I would write about programming, books, anime, life, personal ideas, jokes, space, science, rants, whatever. It happened several times that I was looking for a solution to a problem and found myself explaining it in an older post. People still praise some posts because they refer technology that is maybe a decade old. Others for getting the full picture on how I got to the end result. So for all these vanishing blogs, I feel a sense of loss for all the knowledge that was lost, for all the voices that turned silent.

I know that as a blog dies ten others appear, but there is no sense of origin anymore, no chronological timeline of the evolution of the person writing. I can even go down the "they are not making them like they used to" road. For me a blog would have functioned as a sort of resumé of someones's work. If I liked an article, I would look at others, maybe subscribe. This way I would be connected not with a concept, but with a person: as they grew, I grew. And SEO be damned, I don't care people don't discover my blog anymore because Google can't make up its mind on what I am actually writing about. When people do come, they see me, not just disparate out of context solutions to their 5 minute problems.

So I wrote this article to express my sorrow. I guess that I miss my friends, even if they never knew me.

Some times you need to repeat a code block a number of times and the solution is often a for block.

for (var i=0; i<n; i++)...

This is a complex line to write and most importantly obscures the intent of the code. Wouldn't it be better to have some kind of construct that says "repeat N times" and be intuitively easy to understand? Well there is one:

while (n-->0) ...

No, it isn't some C# construct that you have not heard of before, it's a while loop that checks on the value of n, then decrements it. But it looks great! It almost reads as "while n moves to 0". I liked it and I thought I should share.

I am going to discuss in this post an interview question that pops up from time to time. The solution that is usually presented as best is the same, regardless of the inputs. I believe this to be a mistake. Let me explore this with you.

The problem

The problem is simple: given two sorted arrays of very large size, find the most efficient way to compute their intersection (the list of common items in both).

The solution that is given as correct is described here (you will have to excuse its Javiness), for example. The person who provided the answer made a great effort to list various solutions and list their O complexity and the answer inspires confidence, as coming from one who knows what they are talking about. But how correct is it? Another blog post describing the problem and hinting on some extra information that might influence the result is here.

Implementation

Let's start with some code:

var rnd = new Random();
var n = 100000000;
int[] arr1, arr2;
generateArrays(rnd, n, out arr1, out arr2);
var sw = new Stopwatch();
sw.Start();
var count = intersect(arr1, arr2).Count();
sw.Stop();
Console.WriteLine($"{count} intersections in {sw.ElapsedMilliseconds}ms");

Here I am creating two arrays of size n, using a generateArrays method, then I am counting the number of intersections and displaying the time elapsed. In the intersect method I will also count the number of comparisons, so that we avoid for now the complexities of Big O notation (pardon the pun).

As for the generateArrays method, I will use a simple incremented value to make sure the values are sorted, but also randomly generated:

private static void generateArrays(Random rnd, int n, out int[] arr1, out int[] arr2)
{
    arr1 = new int[n];
    arr2 = new int[n];
    int s1 = 0;
    int s2 = 0;
    for (var i = 0; i < n; i++)
    {
        s1 += rnd.Next(1, 100);
        arr1[i] = s1;
        s2 += rnd.Next(1, 100);
        arr2[i] = s2;
    }
}

Note that n is 1e+7, so that the values fit into an integer. If you try a larger value it will overflow and result in negative values, so the array would not be sorted.

Time to explore ways of intersecting the arrays. Let's start with the recommended implementation:

private static IEnumerable<int> intersect(int[] arr1, int[] arr2)
{
    var p1 = 0;
    var p2 = 0;
    var comparisons = 0;
    while (p1<arr1.Length && p2<arr2.Length)
    {
        var v1 = arr1[p1];
        var v2 = arr2[p2];
        comparisons++;
        switch(v1.CompareTo(v2))
        {
            case -1:
                p1++;
                break;
            case 0:
                p1++;
                p2++;
                yield return v1;
                break;
            case 1:
                p2++;
                break;
        }

    }
    Console.WriteLine($"{comparisons} comparisons");
}

Note that I am not counting the comparisons of the two pointers p1 and p2 with the Length of the arrays, which can be optimized by caching the length. They are just as resource using as comparing the array values, yet we discount them in the name of calculating a fictitious growth rate complexity. I am going to do that in the future as well. The optimization of the code itself is not part of the post.

Running the code I get the following output:

19797934 comparisons
199292 intersections in 832ms

The number of comparisons is directly proportional with the value of n, approximately 2n. That is because we look for all the values in both arrays. If we populate the values with odd and even numbers, for example, so no intersections, the number of comparisons will be exactly 2n.

Experiments

Now let me change the intersect method, make it more general:

private static IEnumerable<int> intersect(int[] arr1, int[] arr2)
{
    var p1 = 0;
    var p2 = 0;
    var comparisons = 0;
    while (p1 < arr1.Length && p2 < arr2.Length)
    {
        var v1 = arr1[p1];
        var v2 = arr2[p2];
        comparisons++;
        switch (v1.CompareTo(v2))
        {
            case -1:
                p1 = findIndex(arr1, v2, p1, ref comparisons);
                break;
            case 0:
                p1++;
                p2++;
                yield return v1;
                break;
            case 1:
                p2 = findIndex(arr2, v1, p2, ref comparisons);
                break;
        }

    }
    Console.WriteLine($"{comparisons} comparisons");
}

private static int findIndex(int[] arr, int v, int p, ref int comparisons)
{
    p++;
    while (p < arr.Length)
    {
        comparisons++;
        if (arr[p] >= v) break;
        p++;
    }
    return p;
}

Here I've replaced the increment of the pointers with a findIndex method that keeps incrementing the value of the pointer until the end of the array is reached or a value larger or equal with the one we are searching for was found. The functionality of the method remains the same, since the same effect would have been achieved by the main loop. But now we are free to try to tweak the findIndex method to obtain better results. But before we do that, I am going to P-hack the shit out of this science and generate the arrays differently.

Here is a method of generating two arrays that are different because all of the elements of the first are smaller than the those of the second. At the very end we put a single element that is equal, for the fun of it.

private static void generateArrays(Random rnd, int n, out int[] arr1, out int[] arr2)
{
    arr1 = new int[n];
    arr2 = new int[n];
    for (var i = 0; i < n - 1; i++)
    {
        arr1[i] = i;
        arr2[i] = i + n;
    }
    arr1[n - 1] = n * 3;
    arr2[n - 1] = n * 3;
}

This is the worst case scenario for the algorithm and the value of comparisons is promptly 2n. But what if we would use binary search (what in the StackOverflow answer was dismissed as having O(n*log n) complexity instead of O(n)?) Well, then... the output becomes

49 comparisons
1 intersections in 67ms

Here is the code for the findIndex method that would do that:

private static int findIndex(int[] arr, int v, int p, ref int comparisons)
{
    var start = p + 1;
    var end = arr.Length - 1;
    if (start > end) return start;
    while (true)
    {
        var mid = (start + end) / 2;
        var val = arr[mid];
        if (mid == start)
        {
            comparisons++;
            return val < v ? mid + 1 : mid;
        }
        comparisons++;
        switch (val.CompareTo(v))
        {
            case -1:
                start = mid + 1;
                break;
            case 0:
                return mid;
            case 1:
                end = mid - 1;
                break;
        }
    }
}

49 comparisons is smack on the value of 2*log₂(n). Yeah, sure, the data we used was doctored, so let's return to the randomly generated one. In that case, the number of comparisons grows horribly:

304091112 comparisons
199712 intersections in 5095ms

which is larger than n*log₂(n).

Why does that happen? Because in the randomly generated data the binary search find its worst case scenario: trying to find the first value. It divides the problem efficiently, but it still has to go through all the data to reach the first element. Surely we can't use this for a general scenario, even if it is fantastic for one specific case. And here is my qualm with the O notation: without specifying the type of input, the solution is just probabilistically the best. Is it?

Let's compare the results so far. We have three ways of generating data: randomly with increments from 1 to 100, odds and evens, small and large values. Then we have two ways of computing the next index to compare: linear and binary search. The approximate numbers of comparisons are as follows:

RandomOddsEvensSmallLarge

Linear	2n	2n	2n
Binary search	3/2*n*log(n)	2*n*log(n)	2*log(n)

Alternatives

Can we create a hybrid findIndex that would have the best of both worlds? I will certainly try. Here is one possible solution:

private static int findIndex(int[] arr, int v, int p, ref int comparisons)
{
    var inc = 1;
    while (true)
    {
        if (p + inc >= arr.Length) inc = 1;
        if (p + inc >= arr.Length) return arr.Length;
        comparisons++;
        switch(arr[p+inc].CompareTo(v))
        {
            case -1:
                p += inc;
                inc *= 2;
                break;
            case 0:
                return p + inc;
            case 1:
                if (inc == 1) return p + inc;
                inc /= 2;
                break;
        }
    }
}

What am I doing here? If I find the value, I return the index; if the value is smaller, not only do I advance the index, but I also increase the speed of the next advance; if the value is larger, then I slow down until I get to 1 again. Warning: I do not claim that this is the optimal algorithm, this is just something that was annoying me and I had to explore it.

OK. Let's see some results. I will decrease the value of n even more, to a million. Then I will generate the values with random increases of up to 10, 100 and 1000. Let's see all of it in action! This time is the actual count of comparisons (in millions):

Random10Random100Random1000OddsEvensSmallLarge

Linear	2	2	2	2	2
Binary search	30	30	30	40	0.00004
Accelerated search	3.4	3.9	3.9	4	0.0002

So for the general cases, the increase in comparisons is at most twice, while for specific cases the decrease can be four orders of magnitude!

Conclusions

Because I had all of this in my head, I made a fool of myself at a job interview. I couldn't reason all of the things I wrote here in a few minutes and so I had to clear my head by composing this long monstrosity.

Is the best solution the one in O(n)? Most of the time. The algorithm is simple, no hidden comparisons, one can understand why it would be universally touted as a good solution. But it's not the best in every case. I have demonstrated here that I can minimize the extra comparisons in standard scenarios and get immense improvements for specific inputs, like arrays that have chunks of elements smaller than the next value in the other array. I would also risk saying that this findIndex version is adaptive to the conditions at hand with improbable scenarios as worst cases. It works reasonable well for normally distributed arrays, it does wonders for "chunky" arrays (in this is included the case when one array is much smaller than the other) and thus is a contender for some kinds of uses.

What I wanted to explore and now express is that finding the upper growth rate of an algorithm is just part of the story. Sometimes the best implementation fails for not adapting to the real input data. I will say this, though, for the default algorithm: it works with IEnumerables, since it never needs to jump forward over some elements. This intuitively gives me reason to believe that it could be optimized using the array/list indexing. Here it is, in IEnumerable fashion:

private static IEnumerable<int> intersect(IEnumerable<int> arr1, IEnumerable<int> arr2)
{
    var e1 = arr1.GetEnumerator();
    var e2 = arr2.GetEnumerator();
    var loop = e1.MoveNext() && e2.MoveNext();
    while (loop)
    {
        var v1 = e1.Current;
        var v2 = e2.Current;
        switch (v1.CompareTo(v2))
        {
            case -1:
                loop = e1.MoveNext();
                break;
            case 0:
                loop = e1.MoveNext() && e2.MoveNext();
                yield return v1;
                break;
            case 1:
                loop = e2.MoveNext();
                break;
        }

    }
}

Extra work

The source code for a project that tests my various ideas can be found on GitHub. There you can find the following algorithms:

• Standard - the O(m+n) one described above
• Reverse - same, but starting from the end of the arrays
• Binary Search - looks for values in the other array using binary search. Complexity O(m*log(n))
• Smart Choice - when m*log(n)<m+n, it uses the binary search, otherwise the standard one
• Accelerating - the one that speeds up when looking for values
• Divide et Impera - recursive algorithm that splits arrays by choosing the middle value of one and binary searching it in the other. Due to the complexity of the recursiveness, it can't be taken seriously, but sometimes gives surprising results
• Middle out - it takes the middle value of one array and binary searches it in the other, then uses Standard and Reverse on the resulting arrays
• Pair search - I had high hopes for this, as it looks two positions in front instead of one. Really good for some cases, though generally it is a bit more than Standard

The testing tool takes all algorithms and runs them on randomly generated arrays:

1. Lengths m and n are chosen randomly from 1 to 1e+6
2. A random number s of up to 100 "spikes" is chosen
3. m and n are split into s+1 equal parts
4. For each spike a random integer range is chosen and filled with random integer values
5. At the end, the rest of the list is filled with any random values

Results

For really small first array, the Binary Search is king. For equal size arrays, usually the Standard algorithm wins. However there are plenty of cases when Divide et Impera and Pair Search win - usually not by much. Sometimes it happens that Accelerating Search is better than Standard, but Pair Search wins! I still have the nagging feeling that Pair Search can be improved. I feel it in my gut! However I have so many other things to do for me to dwell on this.

Maybe one of you can find the solution! Your mission, should you choose to accept it, is to find a better algorithm for intersecting sorted arrays than the boring standard one.