• 22 Dec 2009 /  Life

    On the 16th, while travelling north to Maine for the holidays, I spent the better part of a day wandering around downtown Boston. I made a point to visit the New England Holocaust Memorial there – and snagged a few photos.

    The memorials made up of 6 glass pillars

    The memorial's made up of 6 glass pillars.

    A closer shot of the pillars

    A closer shot of the pillars.


    Yet another closer shot.

    Theres a walkway that goes through all of the pillars.

    There's a walkway that goes through all of the pillars.

    The panes of glass on the pillars are engraved with numbers, symbolizing the numbers that the Jews were branded with.

    The panes of glass on the pillars are engraved with the numbers, symbolizing the numbers that the Jews were branded with.


    A closer shot of the engraved numbers.


    Another shot of the engraved numbers.

  • 29 Nov 2009 /  Code, Technology

    I’ve had a couple discussions lately discussing the difference in speed between accessing data from memory and disk. In most of these conversations people were surprised to know that there is something faster than Main Memory that the programmer can take advantage of .

    First, let’s consider the memory hierarchy. If you do a google image search for memory hierarchy, you’ll see a few different (and very insightful) interpretations. In it’s simplest, it looks like this.

    A version of the memory hierachy. L0 = Level 0, L1 = Level 2, and so on. It should be noted that some high-end systems have a third SRAM Cache, which becomes L3. This causes L3 (Main Memory) to become L4 and L4 to become L5.

    A version of the memory hierarchy. L0 = Level 0, L1 = Level 2, and so on. It should be noted that some high-end systems have a third SRAM Cache, which becomes L3. This causes L3 (Main Memory) to become L4 and L4 to become L5. Also, please also keep in mine that the higher you move up the memory hierarchy, the more monetarily expensive things become (5 GB of RAM is more expensive than 5 GB of hard disk space).

    Main memory is DRAM, while Level 2 (L2) Cache is SRAM. Now, I hear you asking, “What about my SDRAM? Is that the best of both worlds?” No, it’s still DRAM. The S means something different.

    • DRAM: Dynamic Random Access Memory
    • SRAM: Static Random Access Memory
    • SDRAM: Synchronous Dynamic Random Access Memory
    • DDR SDRAM: Double Data Rate & one hell of an acronym.

    If you want to access something on your hard disk, it takes roughly 100,000 times longer than DRAM, and 1,000,000 times longer than SRAM, Making SRAM ~ 10x faster than DRAM.

    There are actually two, and in some machines even three, levels of SRAM Cache. L1 actually lives on-board the processor, while L2 (and the less common L3) live off-board. Although they’re typically all SRAM, in this post references to “SRAM” specifically mean L2 Cache.

    Now I hear you say “Awesome! I’m building this killer machine, and it’s got all the Main Memory it can handle, but I’ve still got some money to burn. Can I increase it’s SRAM too?” No. SRAM (L2 Cache) lives in a piece of additional hardware on your motherboard, you can’t really do anything to it.

    So what’s it all about then? In general, the majority of your accesses to memory will be very close, even adjacent, to your previous access. It won’t always be the case, but it probably will. Caches take advantage of this probability. If you access memory location [x], there is a high probability that you’re next memory access will be to memory location [x+1] or something similar. If you accessed an int in memory, which has a typical size of 4 bytes, then your next memory access will probably  be [x+4]. If L2 Cache is nearly 10x faster, as we know what you’re probably access next, we can speed things up by automatically moving what you’ll probably move into L2 Cache. When your program makes it’s next memory request, we check to see if it’s already in L2. If it is (cache hit) great! If it’s not, (cache miss), too bad – we goto main memory and swap that and it’s adjacent bytes, into L2 and proceed. A typical Intel Pentium chip has 128 KB – 2 MB of L2 Cache, and typically swaps data in and out of cache from main memory in 32 byte chunks.

    So how can a programmer take advantage of this? If you’re going to be accessing chunks of memory, try to access it as you know it appears spatially in memory.

    Let us consider the loop below, and assume for sake of example,

    • Length = 8
    • Any given array[i], an integer, is 4 bytes
    • L2 Cache swaps data in 16 byte chunks (as opposed to the actual 32, noted above. That’s 4 integers).
    • At the start of the loop, the L2 Cache was empty (cold cache).

    [cc lang="cpp"]
    int sumArray(int array[Length])
    {
    int sum = 0;
    for (int i = 0; i < Length; i++)
    sum += array[i];
    return sum;
    }
    [/cc]
    The below table represents cache hits and misses. White are cache hits, and red are cache misses.

    array[i] i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8
    Access Order 1 2 3 4 5 6 7 8

    This is the best that we can do. Now let us consider a 2 dimensional array, given the assumtions

    • Rows = 8
    • Columns = 4
    • C stores arrays/matrices in row-major order.
    • The rest is the same as the example above.

    [cc lang="c++"]
    int sumMatrix(int matrix[Columns][Rows])
    {
    int sum = 0;
    for (int col = 0; col < Columns; col++)
    for (int row = 0; row < Rows; row++)
    sum += matrix[col][row];
    return sum;
    }
    [/cc]

    Let’s look at those cache hits and misses. The values in the table body are the order in which matrix[col][row] was accessed.

    matrix[col][row] row=0
    row=1
    row=2
    row=3 row=4 row=5 row=6 row=7
    col = 0 1 2
    3 4 5 6 7 8
    col = 1 9 10 11 12 13 14 15 16
    col = 2 17 18 19 20 21 22 23 24
    col = 3 25 26 27 28 29 30 31 32

    Now let us consider the case where we do nothing except swap the order in which we access the matrix elements, and inspect the cache hit/miss table.
    [cc lang="c++"]
    int sumMatrix(int matrix[Columns][Rows])
    {
    int sum = 0;
    for (int row = 0; row < Rows; row++)
    for (int col = 0; col < Columns; row++)
    sum += matrix[col][row];
    return sum;
    }
    [/cc]

    matrix[col][row] row=0 row=1 row=2 row=3 row=4 row=5 row=6 row=7
    col=0 1 2 3 4 5 6 7 8
    col=1 9 10 11 12 13 14 15 16
    col=2 17 18 19 20 21 22 23 24
    col=3 25 26 27 28 29 30 31 32

    Every access is a cache miss! Meaning that we have to goto main memory for every access of the matrix. This will be approximately 9 times slower than if we hadn’t swapped the row/column order. This is because data is not actually stored as a two dimensional matrix in main memory – everything is a linear array, with row and column offsets being calculated. Because some data resides right next to other data in main memory, it will also appear this way when 32 bytes are moved into the cache. If you access them in the same order in which they’re stored in main memory, you can take advantage of the cache. If you don’t, you end up forcing cache two swap stuff in and out from main memory.

    John Carmack was once quoted as saying “Low level programming is good for the programmer’s soul”.

  • 25 Nov 2009 /  Life

    “Oh, I’m bad at math, haha“.

    I can’t count the number of times that I’ve heard this, and I’m sure you can’t either. I hear this all the time. I say I’m bad at math, but that’s because I had my [explative] handed to me on a plate in equations (which, as my calculus II professor put it, are “a whole new world of pain”). But when I hear a lot of people say that they’re bad at math, what they mean, is they can’t figure out 50% of 150. But that’s okay, cause they’re bad at math, haha.

    What I’d like to particularly note is that people usually laugh after saying they’re bad at math. In fact, it’s “cool” to suck at math. “Oh, that math crap is hard and is for nerds and losers. I hate it, haha” I hear too often. I can appreciate a certain aversion to academics (yes, there have been times when I have cursed class, any class). However,  math, especially at the algebra level, is a basic enough skill that everyone should have at least a basic understanding and ability. Furthermore, it should not be “cool” to hate it.

    My discrete math professor said something that I’ll never forget:

    “Why is it that people think it’s cool or funny to suck at math? That’s like saying ‘Oh, I can’t read, I suck at reading, haha.’ People are ashamed to say they can’t read.”

    The catalyst to this post was something that I saw over on Wil Wheaton’s blog today in which he indicated that he’s not as good at math as he used to be. Look at point 5 in his post, which expands upon

    “I mean, I’m a pretty smart guy, and there are times when I have to write down a math problem that I used to be able to do in my head, and some of the spelling and grammar errors I make are just embarrassing – and I’m a writer! So my idea is for an 8 week class that meets once or twice a week for a couple hours, that would be a mental tune up for guys like me.”

    This sounds like a fantastic idea, one which I’d probably attend. I love the idea that he wants to be better at math! In fact, I think that there might be something more here. There are all sorts of interest groups, organizations, and events that exist on a national level: hackerspaces, FabLab, MakerFair, ACM, IEEE, etc… Why can’t there be some sort of organization or group that offers adult oriented refresher course? I’d be more than happy to brainstorm with anyone who’d like to with me.

    Tags: ,

  • 22 Oct 2009 /  Life, Order vs Chaos, Technology

    Yeah, we all pretty much agree, aviation checklists are good. It’s reasonable, it’s smart, it just plain makes sense. Conversely, most of us have seen Office Space (or, we got that memo) and agree that, never mind TPS reports themselves, TPS Cover Sheets are stupid mindless paperwork keeping us from just gettin’ on with our jobs! Most people probably have not actually dealt with a TPS Report, per se, but we’re familiar with the metaphor – stupid worthless paperwork.

    So what am I getting at? Aviation Checklists and TPS Report Cover Sheets are really the same thing.

    tpscover
    Aviation Checklist (Yup, there’s an App for that!) TPR Report Cover Sheet (did you get that memo?)

    The purpose of the aviation check list is pretty straight forward. To keep you un-deadified.The purpose of the TPS Cover is a little more convoluted, but it’s essentially a management checklist.

    So how did the aviation checklist come into being? Did someone, one day, say for no reason “Let’s have a checklist. Yeah!”. No. First, somebody messed up. Bad. Then, people got together and had a meeting to discuss what went wrong and how to solve the problem.

    A similar history lies behind much “mindless” paperwork similar to TPS Covers. A young or growing company, without the proper process or individual accountability, can turn a team of young, energetic, and enthusiastic recent college grads into a collection of sleep-deprived jaded suicidal alcoholics in mere days. After one, or more, projects have missed deadlines horribly, a meeting is called. In that meeting it’s asked “Why was the project so late? The original time line still looks reasonable – something went wrong. How can we fix this?”. The answer is often more process, more checklists, more paperwork.

    So, TPS Cover Sheets are the end result of a project (or three) gone wrong. As much as a pain as they may be, they may actually be saving you from being driven into a jaded state of suicidal alcoholism. Conversely, there’s definitely the possibility that too much process and paperwork comes out of the meeting – perhaps an email to an email list for a memo for the coversheet for the tps report, which is ultimately for the test process for the actual product. There’s obviously a balance, but TPS Report Cover Sheets are probably not as bad as Peter Gibbons would have you believe. In the end – Damn, it feels good to be a gansta.

    Tags: , , , ,

  • 19 Oct 2009 /  Life

    Just a few night-pics of my city. Click on any image for full-resolution version.

    San Diego Night Skyline

    San Diego Night Skyline

    San Diego Skyline, Zoomed In

    San Diego Skyline, Zoomed In

    San Diego Gaslamp Quarter, Downtown

    San Diego Gaslamp Quarter, Downtown

    Downtown San Diego, 6th Ave & C St

    Downtown San Diego, 6th Ave & C St

    Tags: , ,

  • 02 Oct 2009 /  Code, Technology

    A lot of people don’t like to put their e-mail address directly on a web-page. You may have seen e-mail addresses that look like “jondoeATgmailDOTcom”, or “j o h n do e @ gma il . c o m!”. Strangeness such as spelling out words like “AT”, odd spaces, or non e-mail address characters such as ! are all tricks employed to avoid having your e-mail address scopped up by someone looking to spam you.

    The way in which I approach the problem is by having javascript write my e-mail address for me. I get both a well formed and clickable e-mail link, as well as avoid getting my e-mail address scooped up by a web crawler. Now, I know that the javascript document.write() function is shunned in most circles, but below is some example code.
    [cc lang="javascript"]
    // File is contactInfo.js
    document.write(”David Kennedy:
    Web
    http://davidwkennedy.com|
    E-Mail dave@orderinchaos.org |
    Phone: 435.770.6865 “);
    [/cc]
    Which is then called in the HTML file as seen below
    [cc lang="html"]

    [/cc]
    I’m sure that it’s probably quite possible to write a web crawler that will be smart enough to pick it up, but I think most web crawlers won’t.

    For example, when I use the web crawler below on my personal site davidwkennedy.com you can see that the results do not contain my e-mail address!

    Below is a web crawler, written in Python & borrowed from IBM’s site on web spiders.
    [cc lang="python"]
    #!/usr/local/bin/python

    import httplib
    import sys
    import re
    from HTMLParser import HTMLParser

    class miniHTMLParser( HTMLParser ):

    viewedQueue = []
    instQueue = []

    def get_next_link( self ):
    if self.instQueue == []:
    return ”
    else:
    return self.instQueue.pop(0)

    def gethtmlfile( self, site, page ):
    try:
    httpconn = httplib.HTTPConnection(site)
    httpconn.request(”GET”, page)
    resp = httpconn.getresponse()
    resppage = resp.read()
    except:
    resppage = “”

    return resppage

    def handle_starttag( self, tag, attrs ):
    if tag == ‘a’:
    newstr = str(attrs[0][1])
    if re.search(’http’, newstr) == None:
    if re.search(’mailto’, newstr) == None:
    if re.search(’htm’, newstr) != None:
    if (newstr in self.viewedQueue) == False:
    print ” adding”, newstr
    self.instQueue.append( newstr )
    self.viewedQueue.append( newstr )
    else:
    print ” ignoring”, newstr
    else:
    print ” ignoring”, newstr
    else:
    print ” ignoring”, newstr

    def main():

    if sys.argv[1] == ”:
    print “usage is ./minispider.py site link”
    sys.exit(2)

    mySpider = miniHTMLParser()

    link = sys.argv[2]

    while link != ”:

    print “\nChecking link “, link

    retfile = mySpider.gethtmlfile( sys.argv[1], link )
    mySpider.feed(retfile)
    link = mySpider.get_next_link()

    mySpider.close()

    print “\ndone\n”

    if __name__ == “__main__”:
    main()
    [/cc]
    Below are the results of the above crawler on davidwkennedy.com
    [cc lang="bash"]
    dave@dave-sparta:~$ python miniCrawler.py davidwkennedy.com /

    Checking link /
    adding index.htm
    adding photos.htm
    adding videos.htm
    adding projects.htm
    ignoring http://orderinchaos.davidwkennedy.com
    adding funstuff.htm
    adding about.htm
    ignoring http://twitter.com/davidwkennedy
    ignoring statcounter

    Checking link index.htm
    Checking link photos.htm
    Checking link videos.htm
    Checking link projects.htm
    Checking link funstuff.htm
    Checking link about.htm
    done

    dave@dave-sparta:~$

    [/cc]

    Tags: , , , ,

  • 27 Sep 2009 /  Technology
    Microsoft's BarrelFish Multi-Kernel Operating System Architecture.

    Microsoft's BarrelFish Multi-Kernel Operating System Architecture.

    Microsoft has a new pet-project: Barrelfish, a multi-kernel operating system (via OS News). As a bit of back story, a kernel is the meat of an operating system. The kernel is largely responsible for enabling other software to make use of hardware.

    In the research team’s article The Multikernel: A new OS architecture for scalable multicore systems they write “We investigate a new OS structure, the multikernel, that treats the machine as a network of independent cores, assumes no inter-core sharing at the lowest level, and moves traditional OS functionality to a distributed system of processes that communicate via message-passing,”.

    This is really good stuff! From a hardware perspective, this is exactly where the future is headed. When I took “Distributed & Network Programming” I remember the class getting Dr. Allan off on a tangent about how a single computer these days is really a distributed system.

    A “distributed system” is generally thought of multiple computers networked together and working together. This idea was popularized when “a computer” was a pretty straight forward idea. A computer consisted of a processor, some main memory, possibly some persistent memory, and some input/output. Today’s computers are much more complex. A video card often has it’s own dedicated main-memory and set of multiple-processors. Hard disk drives are beginning to contain embedded systems to encrypt data saved on the disks. Even main memory is not a straightforward concept these days, not with virtual memory which requires and additional piece of hardware called a memory management unit. A “personal computer” is a series of smaller computers (video cards, hard drives, processors, etc…) networked together. This will be a continuing trend, which will require much more complex operating systems to manage the hardware. This is why I’m so excited over BarrelFish!

    I think the Dinosaur Book will be needing a new chapter! (aaaaawww yeeeaaahhh… the Dinosaur Book – you know it!)

    I hope Microsoft Open-Sources BarrelFish like they did Singularity, which was their research OS
    in which the kernel, device drivers, and applications were all written in managed code.

    Tags: , , , , ,

  • 22 Sep 2009 /  Code, Technology

    Here’s yet another old C# code snipped from my antiquated and dead blog. But throwin’ this out there for anyone who might find it helpful.

    [cc lang="csharp" tab_size="2"]
    try
    {
    string newTime;
    System.Net.Sockets.TcpClient t =
    new System.Net.Sockets.TcpClient(”time-a.nist.gov”, 13);
    System.IO.StreamReader rd = new System.IO.StreamReader(t.GetStream());
    newTime = rd.ReadToEnd();

    string[] times = newTime.Split(’ ‘); // Parses The String
    rd.Close();
    t.Close();
    Console.WriteLine(”Todays Date Is: ” + times[1]);
    }
    [/cc]

    I read somewhere that in order for this code to work, the TCP client has to be installed and enabled in Windows Vista. The TCP client is not, be default, enabled in Vista. To install it, Control Panel — Programs and Features — Turn Windows Features On or Off — TCP Client.

    However, I tried this after unchecking my TCP client and it still worked – so maybe it’s just an old wive’s tale! I’d suggest trying it without the TCP client installed – but don’t count on it working if you’re planning on distributing this without further research.

    The second line after the opening try { has ” time-a.nist.gov”, which is the time server. You can swap this out with some of the other time servers below.If you were feeling ambitious, you might try creating a class that will try a random time server on it’s first try and then randomly try other time servers if the first x fail.

    Name | IP | Location
    time-a.nist.gov | 129.6.15.28 | NIST, Gaithersburg, Maryland
    time-b.nist.gov | 129.6.15.29 | NIST, Gaithersburg, Maryland
    time-a.timefreq.bldrdoc.gov| 132.163.4.101 | NIST, Boulder, Colorado
    time-b.timefreq.bldrdoc.gov | 132.163.4.102 | NIST, Boulder, Colorado
    time-c.timefreq.bldrdoc.gov | 132.163.4.103 | NIST, Boulder, Colorado
    utcnist.colorado.edu | 128.138.140.44 | University of Colorado, Boulder
    time.nist.gov | 192.43.244.18 | NCAR, Boulder, Colorado
    time-nw.nist.gov | 131.107.1.10 | Microsoft, Redmond, Washington
    nist1.datum.com | 209.0.72.7 | Datum, San Jose, California
    nist1.dc.certifiedtime.com | 216.200.93.8 | Abovnet, Virginia
    nist1.nyc.certifiedtime.com | 208.184.49.9 | Abovnet, New York City
    nist1.sjc.certifiedtime.com | 208.185.146.41 | Abovnet, San Jose, California

    Tags: , , , ,

  • 21 Sep 2009 /  Code, Technology

    This is an older post, from another [now dead] blog of mine, but I thought I’d throw it up here as well.

    When working in C#, if you are trying to load a jpeg file and you use the System.Drawing.Image.FromFile method on a file that you do not have the proper permissions for, you will get an “Out of Memory” exception. Somewhat misleading – but that is the error resulting from improper permissions.

    I found a web site that claimed that you create a FileStream object from your file and then use the FromStream method on the Image object.

    My solution for loading a file was as follows
    [cc lang="csharp"]
    private void addPhotoButton_Click(object sender, EventArgs e)
    {
    DialogResult newPhoto;
    Image newPhotoImage;
    string newPhotoFileName;
    newPhoto = openFileDialogAddPhoto.ShowDialog();
    if(newPhoto == DialogResult.OK)
    {
    newPhotoFileName = openFileDialogAddPhoto.FileName;
    FileStream photoStream =
    new FileStream(newPhotoFileName,
    FileMode.Open, FileAccess.Read);
    newPhotoImage = Image.FromStream(photoStream);
    }
    }
    [/cc]

    Tags: , ,