.NET (304) administrative (42) Ajax (42) AngularJS (2) ASP.NET (146) bicycle (2) books (204) browser (10) C# (138) cars (1) chess (30) CodePlex (11) Coma (8) database (58) deployment (3) Entity Framework (2) essay (120) flash/shockwave (2) flex (1) food (3) friend (2) game (22) idea (5) IIS (8) javascript (85) LInQ (2) Linux (6) management (4) manga (46) misc (724) mobile (1) movies (104) MsAccess (1) murder (2) music (64) mysql (1) news (101) NuGet (1) permanent (1) personal (68) PHP (1) physics (2) picture (345) places (12) politics (15) programming (529) question (2) rant (123) religion (3) science (44) Sharepoint (3) software (60) space (2) T4 (2) technology (13) Test Driven Development (4) translation (2) VB (2) video (105) Visual Studio (45) web design (47) Windows API (8) Windows Forms (3) Windows Server (6) WPF/Silverlight (64) XML (12)

Monday, July 27, 2015

Ready Player One, by Ernest Cline

Book cover If you were born before the 80s, Ready Player One is going to fill you with melancholy. Ernest Cline combines several classical young adult themes - like a battle versus an oppressive corporate evil, true and pure love, villainy and lack of honor defeated through friendship and good feelings - with (often obscure) geek memes of the 70s and 80s. If you are the kind of person who likes to impress by quoting lines from movies or telling of your adventures in games that are older than your children, this is the book for you. OK, I won't be mean, the book is going to be fun no matter when you were born, but the level of enjoyment may vary.

However, the book is still a young adult book at its core and, besides the overall message that you actually have to make an effort to reach your goals - an often neglected tidbit in young adult books and movies - it reads like one. Young heroes, with enough skill to pass through the challenges of the story, but awkward enough to also be endearing, manage to save the world through the power of their dedication and ideals. Also Chekhov's Gun has been used so much that it left gaping holes in the story. Amazing how random things in the story come perfectly together at the end. Let a bitter Harry Potterish aftertaste.

But let's start with the plot, which is pretty fun. It all happens in a dystopian world where energy reserves dwindled, gasoline became way too scarce and expensive, Elon Musk never happened and most people live their lives in a virtual world called OASIS, created by a brilliant yet reclusive visionary who made sure the system will remain secure and anonymous. Kind of like the Internet, but without the MPAA or the NSA. Yeah, it already sounds like an impossible dream, doesn't it? Well, the maker of the game world dies and leaves his entire estate (hundreds of billions of dollars and complete control over OASIS) to whoever finds the Easter Egg he his inside the game. The heroes of the story are young "egg hunters", while the villains are corporate drones who have been hired to find the egg for their company.

The writing style irked me a little. I know it is Cline's first book, and it certainly was a decent effort, but it had that way of explaining things that I call "fake past" in which the narrator explains things as if he is telling a story from the past. "The OASIS was...". Since this is supposed to happen in the future, it took a while until I could stop feeling irritated by it. However this has the advantage of being very easy to read.

I think it matters a lot if the reader is into cultural references. I could understand some, I could remember some, most of the references in the book, though, were ancient or obscure enough that even I didn't recognize them, and I am a pretty geeky person. I felt rewarded when I could "get it" and frustrated when I didn't, so probably it will be the same for most readers. If you don't care about these things, I think it is better to wait for the movie.

...which is in the works, with Steven Spielberg attached to the project. It might be difficult to put the story on the screen, though, since the book made an effort to describe a future world where everybody is obsessed with this specific period of the late 20th century, kind of like the Star Trek episodes that happened in the past or that required Kirk or Picard to know some specific book from the school curriculum. There is even a Ready Player One web site, that might have some Easter eggs in it (they would be dumb not to program some) but to me it seems both way too geeky and way to social at the same time.

Bottom line: a fun book for geeks. I hope it inspires the younger generations to look at the world a little bit differently, but I don't have my hopes up. My guess is that they will go all 'Meh' on a story that references anything that happened last century.

Wednesday, July 22, 2015

T-SQL: Joining two very large tables (or not) when trying to determine the hierarchical relationship between the records

Update: after another very useful comment from NULLable, I tried several new ideas:
  • range queries - trying to specify that the child StartIp, for example, is not only greater or equal to the parent StartIp, but also less or equal to the parent EndIp. In my case the query didn't go faster and adding new indexes as recommended in the comment made is slower. I believe it is because the range values are not static or just because clustering the start/end IP index is really way faster than any logical implementation of the search algorithm
  • cursor hints - obviously a very important hint that I should add to almost any cursor is LOCAL. A GLOBAL cursor can be accessed from outside the stored procedure and weird things can happen when running the stored procedure twice at the same time. NULLable recommended also STATIC READ_ONLY and FORWARD_ONLY. In truth the performance of the query doesn't really depend on the speed of the cursor, anyway, but I found an article that discusses the various cursor hints and ends up recommending LOCAL FAST_FORWARD. Check it out, it is very informative. My tests showed no real difference in this particular scenario.
  • RI-Tree implementation in SQL - the article that NULLable linked to is amazing! I just don't get it :) I will update this more when I gain more IQ points.

Update 2: I kind of understood the Relational Interval Tree implementation, but I couldn't find a way for it to help me. The code there creates a computed column of the same type as the IP columns then makes a BETWEEN comparison and/or a join or an apply with two table functions. I can't imagine how it could help me since the original query is basically just two BETWEEN conditions. But still a very interesting article.

I wanted to have a database of all Ripe records, in order to quickly determine the Internet Service Provider for an IP. We are discussing IPv4 only, so the structure of the table in the database looked like this:
CREATE TABLE [dbo].[RipeDb](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [StartIp] [bigint] NULL,
  [EndIp] [bigint] NULL,
  [NetName] [nvarchar](450) NULL,
  [StartTime] [datetime2](7) NULL,
  [EndTime] [datetime2](7) NULL,
  [ParentId] [int] NULL)

As you can see, I translate IPs into BIGINT so that I can quickly sort and select stuff. I also added a ParentId column that represents the parent ISP, as you have some huge chunk of IPs, split and sold to other ISPs, which in turn are selling bits of the IP range they own to others and so on. The data I receive, though, is a simple text file with no hierarchical relations.

The task, therefore, is to take a table like described above, with more than four million records, and for each of them find their parent, if any.

The simplest idea is to join the table with itself like this:
SELECT rp.Id as ParentId, 
   r.Id 
FROM   RipeDb r 
   INNER JOIN RipeDb rp 
       ON rp.StartIp <= r.StartIp 
          AND rp.EndIp >= r.EndIp 
          AND rp.EndIp - rp.StartIp > r.EndIp - r.StartIp 
This gets all ancestors for each record, so we need to use a RANK() OVER() in an inner select in order to select only the parent, but that's beyond the scope of the article.

Since we have conditions on the StartIp and EndIp columns, we need an index on them. But which?

Through trial and error, more than anything else, I realised that the best solution is a clustered index on StartIp,EndIp. That is why the first column (Id) is not marked as PRIMARY KEY in the definition of the table, because it has to look like this:
[Id] [int] PRIMARY KEY NONCLUSTERED IDENTITY(1,1) NOT NULL
. Yes, primary keys don't have to be clustered.

But now you hit the snag. The process is EXTREMELY slow. Basically on my computer this query would end in a few days (as opposed to twice as much with a nonclustered index). What the hell is going on?

I tried several things:
  • JOIN hints (Merge, Loop and Hash joins) - the query optimizer seems to choose the best solution anyway
  • Various index combinations - nothing beats a clustered index
  • Taking a bunch of records and joining only them in a WHILE loop - it doesn't fill up the temp db, but it is just as slow, if not worse

At this point I kind of gave up. Days of work trying to figure out why this is going so slow reached a simple solution: 4 million records squared means 16 thousand billion comparisons. No matter how ingenious SQL would be, this will be slow. "But, Siderite, I have tables large like this and joining them is really fast!" you will say. True, with equality the joins are orders of magnitude faster. Probably there is either place for improvement in the way I used the indexes or in the way they are implemented. If you have any ideas, please let me know.

So did I solve the problem? Yes, of course, by not relying on an SQL join. Think about how the ranges are arranged. If we order the IP ranges on their start and end values, you get something like this:



For each range, the following is either a direct child or a sibling. I created a stored procedure that called itself recursively, which should have worked, but then it reached the maximum level of recursion in SQL (32 - a value that one cannot change!) and so I had to do everything myself. How? With a cursor. Here is the final code:
DECLARE @ParentIds TABLE (Id INT,StartIp BIGINT, EndIp BIGINT)
DECLARE @ParentId INT
DECLARE @Id INT
DECLARE @StartIp BIGINT
DECLARE @EndIp BIGINT
DECLARE @OldParentId INT

DECLARE @i INT=0
DECLARE @c INT

DECLARE curs CURSOR LOCAL FAST_FORWARD FOR
SELECT r.Id, r.StartIp, r.EndIp, r.ParentId
FROM RipeDb r
WHERE r.EndTime IS NULL
ORDER BY StartIp ASC, EndIp DESC

OPEN curs

FETCH NEXT FROM curs
INTO @Id, @StartIp, @EndIp, @OldParentId

WHILE @@FETCH_STATUS=0
BEGIN

    DELETE FROM @ParentIds WHERE EndIp<@StartIp

    SET @ParentId=NULL
    SELECT TOP 1 @ParentId=Id FROM @ParentIds 
    ORDER BY Id DESC

    SELECT @c=COUNT(1) FROM @ParentIds

    IF (@i % 1000=0)
    BEGIN

    PRINT CONVERT(NVARCHAR(100),SysUtcDatetime())+' Updated parent id for ' + CONVERT(NVARCHAR(100),@i) +' rows. ' + CONVERT(NVARCHAR(100),@c) +' parents in temp table.'
    RAISERROR ('', 0, 1) WITH NOWAIT

    END
    SET @i=@i+1

    IF (ISNULL(@OldParentId,-1) != ISNULL(@ParentId,-1))
    BEGIN
        UPDATE RipeDb SET ParentId=@ParentId WHERE Id=@Id
    END

    INSERT INTO @ParentIds VALUES(@Id,@StartIp,@EndIp)

    FETCH NEXT FROM curs
    INTO @Id, @StartIp, @EndIp
END

CLOSE curs
DEALLOCATE curs

I will follow the explanation of the algorithm, for people hitting the exact issue that I had, but let me write the conclusion of this blog post: even if SQL is awesome in sorting and indexing, it doesn't mean that is the only solution. In my case, the SQL indexes proved to be a golden hammer that wasted days of my work.

So, the logic here is really simple, which makes this entire endeavour educational, but really frustrating to me:
  1. Sort the table by start IP ascending, then end IP descending - this makes the parents come before the children in the list
  2. Create a table variable to store the previous parents - so when you finished with a range you will automatically find yourself in its parent
  3. Use a cursor to move through all the items and for each one:
  4. Remove all parents that ended before the current item starts - removes siblings for the list
  5. Get the last parent in the list - that is the current parent range
  6. Set the parent id to be the one of the last parent

It's that deceptively simple and the query now ends in 15 minutes instead of days.

Another issue that might be interesting is that after the original import is created, the new records added to the table should be just a few. In that case, the first join and update might work faster! The next thing that I will do is count how many items I need to update and use one method or another based on that.

Hope that helps someone.

Tuesday, July 21, 2015

Villains by Necessity, by Eve Forward

Book cover Villains by Necessity is not a masterpiece of literature, but it is a fun fantasy book that doesn't feel the need to be part of a trilogy or take itself too seriously. Perfect for when you want to pick up a book because you are tired, not because you want to work your brain to dust. First work of Eve Forward, it is rather inconsistent, moving from silly to dead serious and back and making the heroes of the story oscillate between pointlessly evil and uncharacteristically good.

The best part of the book, though, is the concept. The world enjoys an age of light and good after a bitter war that saw all the forces of darkness and evil be defeated. The world is filled with happy people, no conflict, beautiful weather, lush vegetation. In a word, it is fucking boring. An unlikely party of evildoers gets together to save the world by bringing darkness back!

Alas, it was a concept that was not really well used. The characters, borrowed from classical fantasy, are "evil" by their professions only, but not by behaviour. Sam is an assassin, but he doesn't enjoy the suffering of his victims and is proud of his prowess. Archie is a mischievous thief, but other than that he is an OK fellow. Even Valerie, the dark sorceress, eats sentient beings just because it is her race's culture and her evil is more often artificial. Not to mention Blackmail, who acts as the classic stoic hero. Similarly, the forces of good are blood thirsty thugs that want to either kill everything dark or brainwash them, as a humane solution. This basically makes our heroes... err... heroes, not villains, and viceversa.

Now, the book wasn't bad. The style was amateurish, but it is Eve Forward's first book, after all. I could read it and I got caught by the story. I was more attracted to the original concept, though, and I was very curious how it would go. It is so difficult to present bad people as the protagonists, I know, because many people, including writers as they write, want them to be redeemed somehow. In the end, the moral of the story - excruciatingly laid out in a few paragraphs that shouldn't have existed - felt really heavy handed and simplistic. Ok, good people can do bad things and bad people can do good things, but it is important to explore what makes them good and bad, not just lazily assign them dark fantasy classes and be done with it.

Bottom line: fun read, but nothing special.

Sunday, July 19, 2015

We are doomed to be hit by asteroids, repeatedly

This is how reality stands right now: even if the danger of an asteroid hit is great, the risk of one hitting is small. That means that they hit (very) far apart and cause a lot of damage. Now, all governments in the world are run by politicians, who are by their very nature bureaucrats. They are reactive, not proactive, and they have insulated themselves from responsibility by manipulating laws and creating committees and departments that they can behead at any time, as they keep their fat asses on their chairs of power. This is not a rant, it's just the ugly truth, evolving, but never really changing since we were barely smarter than monkeys.

The logical conclusion of these facts is that politicians will not do anything about asteroids until we are hit by one. Even worse, since the probability that a really big one will hit without us knowing in advance has been reduced by space advances, the asteroid that will hit us will probably be small. The Tunguska and the Chelyabinsk events, real things that happened, changed nothing. The one that is going to change anything will be when something similar happens on top of a city.

This is not a doomsday prophecy, either. The probability that this will happen is extremely small. First of all the asteroid has to be small enough and/or fast enough so that we don't detect it in time. Then it has to hit at a certain angle to not be deflected by the atmosphere. Then it has to reach a populated area, which one would think is simple, since we can't seem to be able to fart without someone smelling it, but in truth, with the oceans and the human propensity of congregating for no good reason, it is less probable. However, with enough time, even a small probability becomes certainty.

So, the scenario goes like this: we all pretend to care, but we don't. We want less taxes, not asteroid protection. Politicians use our shortsightedness and our greed to enhance their own and do nothing. Then an asteroid hits, causing massive damage, death and loss of property. This is the moment when something happens. They implement new laws, launch asteroid defense programs, create new departments and committees. But, since the probability that an asteroid hits is small, the hype will fade, the budgets with it, politicians will rotate, people will forget. By the time the next asteroid hits, no one will be prepared for it any more than for the previous one.

In the end, the only things that ever made a dent in the probability that something will hurt us as a species or even as a larger group were technological. Not technology per se, just its price. Just more scientists with cheaper tech getting more done. When space launches become cheaper, satellites smaller, we can do more with them at the same relative price. That is why now we are discovering millions of asteroids in the Solar System, not because of some sort of scientific awakening. It's cheaper, probably as cheap as it was for amateur astronomers to buy telescopes in 1801, when Giuseppe Piazzi discovered the first asteroid, Ceres. I just hope this all gets cheap enough fast enough so we can do something by the time the big asteroid is coming. Well, if we don't destroy ourselves in some other way by then.

I know I'm a month late, but Happy Asteroid Day!

Wednesday, July 15, 2015

Fun debugging stuff

I needed to get all IP addresses in a range, so I applied the mask to my current IP and started to work through the minimum and maximum values of bytes to get the result. I had a code that looked like this:
for (var b = min; b <= max; b++) { //do stuff }
where min was 0 and max was 255.

The expected result: all values from 0 to 255. The result: infinitely running code. Can you spot why?

Yes, when min and max are bytes, b is also a byte, so when it gets to 255 and does b++ the value becomes 0 again. Fun, eh?