And it gets even worse

or the tyranny of the small states

A follow on from post yesterday about the unfairness of the electoral college. I was surprised by how small of minority of the voting population could elect the president of the US. It really is possible with the electoral college that 78.5% percent of voters could be overruled by as few as 21.5% in electing the president of the US. 

Personally, I find the results a bit shocking. But it also made me wonder in which direction we are heading in--towards a more or less fair selection process given future population changes.

So, I went with published estimates of the 2015 population, then extrapolated these into the next census count year (2020). Obviously, there will be a shifting of the electoral college based on changing demographics and this was accounted for in the 2020 census year. The interesting part too is that the electoral college being fixed to the House and Senate and the members of the house have been fixed to 435 members since 1913--all this was taken into account.

What happens is that the skew gets worse (i.e. less fair). Generally because more populated states tend to acquire more people at a larger rate over all. So, the effect on the electoral college selection process in the future is that an even smaller portion of the population can elect the president in the future. In other words the relevancy of the majority in selecting the next president becomes even less relevant.

OK--so the plot:

In 10 years the worst case results in a downward trend of .12% less of the voting population needed to elect the next president. Before you write this off as inconsequential--that .12% represents 400,000 people. That's 400,000 additional people in 2020 that could potentially lose the right to have their vote count. And a further extrapolation of this trend (beyond 2020) just ends up getting worse.

Given that the small states have an disproportionate representation in electing the president due to the electoral college, I like to call this the tyranny of the small states.

The inequity of the electoral college

or potentially how sk(cr)ewed are we?

This presidential election cycle in the US has given me much to think about. Especially post-election. Twice in my lifetime now we've elected a president with less than half of popular vote. When Gore lost in 2000 the margins were close (.5% of the popular vote), it's less so this time with Hillary Clinton standing at roughly 2 million votes and counting (or currently by a margin of 1.5%)

It got me wondering just how this could pencil out that the electoral college can skew the popular vote? I started doing a little research and a little simple math to see just how skewed (or screwed) we could be.

So, the electoral college has a representative for each member of the House and Senate. And that's the reason for the skewed representation. The senate is not based on population. So, out of the 535 votes, 100 are not based on population (one for each member in the Senate). Forget the fact that this approach seems somewhat feudal in approach (where only land-owners were allowed to vote).

Just how sk(cr)ewed are we. Well I grabbed data from the 2010 census, which is used to determine the electoral distribution. And it's ugly.

If we take the largest states and assume they all vote for the losing ticket, then the winning ticket gets the smallest margin of the winning vote, the outcome becomes just 21.5% of the population determining the outcome of the election. This is a highly unrealistic outcome, but theoretically possible. It shows that one-fifth of the population of the United States can select the president of the United States.

The simulation below accumulates the population of the most populous states with a losing electoral count. Then assume the remaining states a simple majority votes the other way (66,298,350).

state: California
state: Texas
state: New York
state: Florida
state: Illinois
state: Pennsylvania
state: Ohio
state: Michigan
state: Georgia
state: North Carolina
state: New Jersey
pop: 175547114, half electoral: 270

That gives the worst skewed case where the minority of 21.5% of the population selects the president. Surely any system that could so poorly represent the wishes of a majority must be broken or open to manipulation.

Random bit slogging notes through some performance issues

OK so I've been spending time over the last year occasionally tweaking performance improvements on a multi-core application. This can be a huge timesink. What works best for me is to gather data, try some obvious changes, then get away from the computer and stew on the problem for a bit.

Obviously for the multi-core world, the one goal here is to support scaling as more cores are thrown at a problem. That has meant that performance tweaking requires:

1.  Avoid locking of any kind, otherwise performance won't scale as more cores are thrown into the stewpot
2. Minimize cache misses or hot cache reloads, increase cache-coherency
3. Old fashion instruction tweaking (i.e. reducing instruction costs). 

The above are listed in their approximate order of importance.

I highly recommend watching the videos listed on this posting as they point out that #2 is often more important that #3 in performance tweaking.

Locking can often be avoided by using userspace RCU, or similar tricks.

 Other great resources:

  Performance bit twiddling
  Awesome parallel programming reference
  Detailed Assembly/C/C++ x86 Optimizations

 Obviously one of the great tools is just running perf top, a great deal of insight can be gained just by looking at the results the command below produces:

 sudo /usr/bin/perf top -p <pid>

Pretty much any kind of hardware/software supported events can be profiled, but by default counts are samples per function.

There are a ton of tools out there to help evaluate performance--just make sure that you understand how the data is being captured and presented otherwise you risk getting sucked down the rabbit-hole of false assumptions...

Awesome! videos on modern CPU performance optimzations

Wow--I finally ended up watching these after sitting on these links for a while. They are just what the doctor ordered if you have questions about low-level source code performance optimizations in modern processors.

Questions on SSE/AVX, pipelining, cache fetch times, memory access, locality of memory access etc. are addressed in these talks. What is fantastic (and repeatedly driven home) is that performance is not necessarily about reducing overall CPU instructions, but reducing memory cache access times (and how to do this).


http://channel9.msdn.com/Events/Build/2014/4-587
http://channel9.msdn.com/Events/Build/2013/4-329


By the way--you can disregard the Microsoft provenance--most of the discussion/techniques equally apply to any modern x86 compiler.

Jo bob says watch'em!

Computing changed bits in a range of values

So, there's a reason to do this, other than just wasting CPU cycles. I need to take in a range of 2 byte values and compute a mask on all changed bits between the lower and upper value of this range.

The underlying reason is this allows for a quick match against network packet port ranges. So below I have a little test app that computes the changed bits given an arbitrary start stop value.

This ends up producing the following output:

slioch@slioch-All-Series:~/vyatta$ ./range 32076 62199
xxxxxxxxxxxxxxxx
slioch@slioch-All-Series:~/vyatta$ ./range 52076 62199
xxxxxxxxxxxxxx--
slioch@slioch-All-Series:~/vyatta$ ./range 62076 62199
xxxxxxxx--------
slioch@slioch-All-Series:~/vyatta$ ./range 1 2
xx--------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 3
xx--------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 4
xxx-------------
slioch@slioch-All-Series:~/vyatta$ ./range 1 1024
xxxxxxxxxxx-----
slioch@slioch-All-Series:~/vyatta$ ./range 1 1023
xxxxxxxxxx------

The "x" represents a bit position that changes, while the "-" represents a position that doesn't change. This ends up allowing for a quick comparison against a start-stop (or range) of values. Note that the representation above has the LSB (least signficant bit) on the left.

#include <string.h>
#include <strings.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <math.h>


#define NUM_BITS_FOUR_BYTES 32

static void
byte_to_binary(unsigned int *x, int num)
{
  unsigned int mask = 0x01;
  int z;
  for (z = 0; z < num; ++z) {
    printf(((*x & mask) == mask) ? "x" : "-");
    mask = mask << 1;
    if (z % NUM_BITS_FOUR_BYTES == (NUM_BITS_FOUR_BYTES - 1)) {
      mask = 0x01;
      x++;
    }
  }
}


/* 
   Calculate fixed/wildcards in ranges of numbers
   for binary representations.
*/
int main(int argc, char **argv)
{
  if (argc < 3) {
    printf("need start and end\n");
    return;  
  }

  long int start = strtoul(argv[1], NULL, 10);
  long int end = strtoul(argv[2], NULL, 10);
  if (end < start) {
    printf("Error in range\n");
    exit(0);
  }

  //now let's see compute all the bits changed in this range
  unsigned int i, accum = 0;
  accum = start ^ end;
  int loc = 32 - __builtin_clz(accum);
  for (i = 0; i < loc; ++i)
    accum |= 0x1 << i;
  byte_to_binary(&accum, 16);
  printf("\n");


}

A little fun with L1/L2/L3 cache RAM fetch speed

I know it has been a while since I've posted. And that's pretty much a reflection of being super busy as well as not having a little nugget at the tips of my fingers to post.

So I'm back.

I wrote the little program below to test the cost of fetching values from lookup tables of various sizes. Presumably this would show up in performance differences once the lookup table exceeds the size of the various cache it could easily fit within.

So, my little experiment went as followed:

Mad Cyclist on Hwy-101

OK, on 12/10 I saw something I would never expect to see on a freeway.

Leading into San Francisco from Silicon Valley (well the Peninsula actually) there was this crazy dude cycling and passing traffic on 101.

OK--it was stop and go kind of speeds, but what the heck! I've got to give this man credit for going for broke when even the most insane of us would say no thanks.

And here's one a little further on--notice that he's actually passing the slow lane:

Cycling from SF to Yosemite

OK, my oldest said I was mad, and she's right. But last week I ended up cycling for 2 days from SF up to Yosemite. It was one of those things that seemed doable knowing what it's like to ride longer distances, but still seemed daunting given the lack of ride support (disclaimer: I've done two double centuries but this was way different).

The hardest part of the trip was the climbing (no kidding), and the heat (turns out to have been over 100 on each day). As my friend texted me during the ordeal: loads of water, electrolytes, food.

The heat and hills combined to double team my sweat glands--you could almost just watch sweat pouring down my arms later in the day.

Getting my VM to talk to the office

Admittedly, without putting too much thought into this I expected to be able to configure a VM located on my home machine to connect to a work computer through an already established VPN tunnel without too much hassle.

Well, I ran into a couple bumps getting this system up and running. To be specific I needed sessions to be initiated from both directions (from work to the local VM, and from the local VM to work).

So, basically, the configuration looked like this: There's a VPN tunnel established between work and my home computer. On the home computer there's a VM that needs to reach a system at work, and the system at work needs to reach the VM at home.

Or similar to the illustration below:

So, I guess why I found this interesting is that it wasn't as simple as I initially thought. First stab was to set up the VM and bridging the network on the VM to the host systems interface. But the bridged VM ended up getting the dhcp advertised default route from my home router and therefore packets would not travel through the VPN tunnel. The routing table on the VM looks like (where 10.0.1.1 is the IP of my home router):

root@debian:~# ip route
10.0.1.0/24 dev eth0  proto kernel  scope link  src 10.0.1.48 
default via 10.0.1.1 dev eth0 

A little perl nugget: differences between two arrays

Something small, simple...

I have two perl arrays and I want to remove all elements in common between the two arrays, leaving only the elements in list_one that are unique to list_one.


For example pre-populate two arrays with the following values.

my @list_one = ();
push(@list_one,'a');
push(@list_one,'b');
push(@list_one,'c');

my @list_two = ();
push(@list_two,'b');

Setting up Perf for performance evaluation of your code

OK--some quick notes on setting up and running linux tools performance profiling (perf):

sudo apt-get install libelf-dev binutils-dev

wget http://www.kernel.org/pub/linux/kernel/v3.0/linux-3.0.4.tar.gz

tar xvfz linux-3.0.4.tar.gz

cd linux-3.0.4/tools/perf/

make

scp /usr/lib/libelf.so.1 [to-target-system]
scp /usr/lib/libbfd-2.20.1-system.20100303.so [to-target-system]


# sudo /opt/bin/perf 

usage: perf [--version] [--help] COMMAND [ARGS]

The most commonly used perf commands are:
annotate        Read perf.data (created by perf record) and display annotated code
archive         Create archive with object files with build-ids found in perf.data file
bench           General framework for benchmark suites
buildid-cache   Manage build-id cache.
buildid-list    List the buildids in a perf.data file
diff            Read two perf.data files and display the differential profile
evlist          List the event names in a perf.data file
inject          Filter to augment the events stream with additional information
kmem            Tool to trace/measure kernel memory(slab) properties
kvm             Tool to trace/measure kvm guest os
list            List all symbolic event types
lock            Analyze lock events
probe           Define new dynamic tracepoints
record          Run a command and record its profile into perf.data
report          Read perf.data (created by perf record) and display the profile
sched           Tool to trace/measure scheduler properties (latencies)
script          Read perf.data (created by perf record) and display trace output
stat            Run a command and gather performance counter statistics
test            Runs sanity tests.
timechart       Tool to visualize total system behavior during a workload
top             System profiling tool.

See 'perf help COMMAND' for more information on a specific command.



to run (C specifies which CPU, and p specifies which process to attach to):

sudo /opt/bin/perf record  -p 4040 -C 5
sudo /opt/bin/perf report -i perf.data

AT&T UVerse fiasco

I hate to complain.

But this is just one I have to post about.

I made the decision to upgrade from AT&Ts DSL service to UVerse--to get a better data rate at a lower price. A reasonable decision--to be made unreasonable by AT&T.

First the UVerse modem was delivered one day after they cut off the old DSL service. OK--so that's a day without service. You'd think they could be a bit more effective at coordinating this, or just cut off service a day later. But I guess as I found out this was to set the stage for further incompetence on AT&T's part.

The next day, with equipment now wired up and showing some signs of life. UVerse still doesn't come up. Turns out the order was written incorrectly. Should have been written to include support for the POTs line, but was written without. I'm guessing that some tech only just needs to unplug the cable from socket A and into socket B. But this new addendum order takes another 24 hours to clear.

HP-15c is on it's way

Available in October according to one reseller.

More details can be found here:

Sounds like it will be limited to 10k. Hopefully the build quality is as good as the original (I have my doubts).

Enjoy.

Something to crow about: Gson Json code generator

Gee Whiz--this is a real time save. Gson is a google project to serialize and deserialize json data. Good enough. The problem is that to do this you really want to drop the deserialized output into a java object for further processing.

There are some generalized object containers out there, but these didn't really do what I was looking for. Guess what I wanted was something lite and easy--no go.

So, here's the whizbang part. This site takes your json, such as:

Network monitoring

I'm on a bit of R and R right now. Have to burn through the vacation time somehow. Earlier, this year I made a point of pushing at least one new blog entry per week. Seems like I missed this week for the first time in a while.

So, perhaps, just to make me feel "whole", here's a link to an article I wrote for Dr. Dobbs a few years back which describes a framework for network monitoring. Basically a cascading set of filters and processors (pipeline), which threading support in each filter manager:

The SecureScout Wi-Fi Security & Monitoring Framework

How to set up an email smtp client to work with smtp.gmail.com

There's a bunch of implementations out there that don't work (possibly outdated or just plain broken. So, that's why I'm publishing this today--so I have a handy reference when I need it again.

Anyways, this one DOES work using gmail as the smtp agent.

Enjoy.

String host = "smtp.gmail.com";
  int port = 587;
  String username = "your_gmail_login";
  String password = "your_password";
  String from = "support@belisarius2000.com";

  Properties props = new Properties();
  props.put("mail.smtp.starttls.enable", "true");
  props.put("mail.smtp.host", host);
  props.put("mail.smtp.user", username);
  props.put("mail.smtp.password", password);
  props.put("mail.smtp.port", "587");
  props.put("mail.smtp.auth", "true");


   Session session = Session.getInstance(props,new 
     GMailAuthenticator(username, password));

   Message message = new MimeMessage(session);
   message.setFrom(new InternetAddress
      ("support@belisarius2000.com"));
   message.setRecipients(Message.RecipientType.TO,
      InternetAddress.parse(email));
   message.setSubject("Hey there dude!");
   message.setText
      ("Here's the body of my email, blah blah blah");
 
   Transport transport = session.getTransport("smtp");
   transport.connect(host, port, username, password);
 
   Transport.send(message);

And this class too...

class GMailAuthenticator extends Authenticator {
  String user;
  String pw;
  public GMailAuthenticator (String username, String password)
  {
    super();
    this.user = username;
    this.pw = password;
  }
  public PasswordAuthentication getPasswordAuthentication()
  {
    return new PasswordAuthentication(user, pw);
  }
}

Steve Job's spaceship

Wow--just had a chance to watch the Cupertino city council presentation by Steve Jobs last night. Did he have them eating out of his hands or what? I had a couple of thoughts, obviously this guy really has a vision. And second these city council reps came off as a bunch of sycophants--what's the point of asking for an ipad for every resident of the Cupertino, or an Apple store for Cupertino. Kind of laughable.

But back to the spaceship. It seems like Apple is really on a roll here. It's a battle between the Big Three: Google, Apple and Facebook for new employees. So, this definitely ups the bidding. I wouldn't be surprised if in the basement there's booster rockets and cryogenic pods to blast off into space once this planet turns into a dustbowl (maybe from too many ipads?) a la Silent Running.

And the video

A C++ Boost client for the Vyatta REST api

Here's a Vyatta REST client I modifed from a stock Boost https client example. In some tests a while back I found that using a remote command line client implemented in C++/c was significantly faster than using a scripted Perl implementation, which makes sense when latency isn't the overwhelming factor in the latency of the response. And as I alluded to, with claims of performance there are other important criteria that come into play, such as latency, jitter, response time on the server, etc. Needless to say I my queue (somewhere) a pending post to quantify this performance difference using different client implementations.

You can see from the help that the executable requires the target, url (i.e. command), and optionally password/username to run.

Usage: vyatta_boost   [options]
  -h  host name or ip
  -c  rest api command path
  -m  HTTP method (i.e. GET, DELETE, POST, PUT)
  -u  username
  -p  password

And running this command:

Huffman and the STL

A while back I wrote a Huffman encoder using the C++ STL (Standard Template Library). It worked, but then a co-worker of mine took it upon himself to see how many lines of code he could squeeze out of my implementation. So, in the intervening years I always had this in the back of my head to revisit this and create a compact Huffman encoder with C++ and STL.

So, given a spare moment I wrote carved out a little chunk of code--probably not the absolute smallest in number of lines, but compact none the less. I'm sure a version in Perl would end up being far more compact, but then it would be written in Perl.

The code ends up looking simple and neat, which is one of things I love about using the STL.

See for yourself. The encoding calculation is below, with what is really just a scan for the frequency of occurrence of an ascii character.

vector ct_coll(256);
for (int i = 0; i < input.length(); ++i) {
  ct_coll[input[i]]._c = input[i];
  ++ct_coll[input[i]];
}
//now sort and build tree
multiset freq_coll;
copy(ct_coll.begin(),ct_coll.end(),inserter(freq_coll,freq_coll.begin()));
while (freq_coll.size() > 1) {
  freq_coll.insert(Data(new Data(*freq_coll.begin()),new Data(*++freq_coll.begin())));
  freq_coll.erase(freq_coll.begin());freq_coll.erase(freq_coll.begin());
}
//assign value
Data d = *freq_coll.begin();
assign_code(d);

How to see sounds with a Ruben's tube (Sound and Fire!)

DISCLAIMER: Nothing in this post is software/code related.

But who cares it's really cool none-the-less.

A bit of background first. I've been working on demonstrating the science of waves at my kids elementary school for the past 3 years now. At about 2 weeks out I start asking myself this question:

What experiment/trick can I perform to help the kids visualize a pressure wave?

We use a slinkys, use a spectrum analyizers, watch a video of the tacoma narrows bridge, etc.But what can I do that really is an attention grabber and helps cement the concept for these grade school kids? And can it rate high on the coolness factor?

So, the idea of building a Ruben's Tube looked light it might fit the bill here. A Ruben's tube basically is an experiement where sound affects fire--how cool is that? Pretty damn cool that's what I say. I asked my cohort (Ross) and wife (who helps to organize the whole affair) if this would fly... And to my complete surprise no one said NO.

So we went off and built us a Ruben's tube...

What exactly is a Ruben's tube? A Ruben's Tube is a length of tube filled with flammable gas (propane) with small regularly spaced holes. The tube is sealed at one end and capped at the other end with a speaker. The gas has nowhere to escape but through these little holes. And the sound (via the speaker) creates a standing wave (at the right frequency that is) that affects the gas pressure along the length of tube. This results is varying flame height based on the location of the hole and the degree of particle motion due to the standing wave. This would be a sine wave of flames along the length of the tube.

When a resonant frequency is pumped into the tube a standing wave will disturb the gas at the points where the motion in the p-wave is the greatest and suppress the gas leaving the tube at holes located at these points. Likewise holes near where the p-wave motion is less will then to escape at a greater velocity.

That mostly makes sense to me (having a bit of a background with acoustics myself).

This required a trip to a local scrapyard (for the tube), the nearby Lowes, and then expropriating a small speaker from Brian's speaker system. And a big ole tank of propane gas. After much drilling, and fitting and drilling we ended up with a 72 hole ruben's tube, about 4 feet in length.

Below we are in the middle of drilling the 72 hole array (that's Ross doing the work with Brian supervising).

The mostly assembled tube is here (sans propane tank connector):

With a closeup of the speaker end of the tube (tube and speaker are 2 inches in diameter):

So, the darn thing worked, but really really wants a sheltered place. Given that no such place exists anywhere in windscape of San Francisco, below video of the contraption working (briefly before the wind gets the better of it). I apologize for the wonky orientation of the video--next time I'll get that straight (the tube really is stationary in a horizontal position). The amplitude modulation of the waves shows up in the last few seconds of the video.

What we discovered what the tube could be shorted (i.e. fewer holes), or we need more pressure and we have to do this in an enclosed space (i.e. NO WIND).

Next up (when I get around to it) will be video of the Ruben's tube playing to "When the levee breaks".