Ned Bingham
Resume, Curriculum Vitae

stdcore: a Toy Container Library

The functionality provided by the algorithm header in the C++ Standard Library is indispensable, but ultimately painful to use. Code that should take only one line ends up taking quite a bit more and is much less readable. This happens for two reasons. First, every function requires an iterator to the first and last elements for each range it operates on. Suppose there were a function foo() that returns a container. This property makes it impossible to call successive algorithms as in x = *max_element(foo()). This instead turns into:

auto y = foo();
auto x = *max_element(y.begin(), y.end());

Second, algorithms only operate on iterators which are unable to add or remove elements to the container. This means that algorithms that normally add or remove elements, like unique(), copy algorithms, merge(), set_difference(), set_difference(), and others, cannot do so. This turns something as simple and common as x = unique(sort(y)) into the following trainwreck.

array<int> x = y;
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());

Finally, something that is a little less of a problem and a little more of a pet peeve. Whenever I need to compare two different containers I have to define the comparison functions in my own code and they always end up the same. For example operator <() tends to look something like this:

iterator i = a.begin();
iterator j = b.begin();
for (; i != a.end() && j != b.end(); i++, j++)
	if (*i < *j)
		return true;
	else if (*i != *j)
		return false;

return j != b.end();

An Alternative

So, after a few years of dealing with this, I developed a toy container library to test out a hunch. I want to emphasize that this is a toy library, not production ready. It has gone through quite a few architectural changes and I haven't been particularly thorough or consistent. It is neither well tested nor is it well documented. It serves only as a proof of concept. That said, it is fairly functional so have fun!

Power to the Iterator

I decided upon giving iterators power to add and remove elements from their parent structure. So, now every iterator must have a pointer to its parent structure and few basic functions. For an iterator i:

This ends up being a very clean interface for interacting with containers. Instead of the Standard library's v.insert(i, x.begin(), x.end()), we get i.append(x). Further, unique(x.begin(), x.end()) can now resize the container as necessary.

Keep in mind, there are a few trade-offs being made with this interface. First, each iterator has to maintain a pointer to its parent which needs to be dereferenced for these functions. Second, calling one of these functions will invalidate other iterators to the same container. This is the same as in the Standard Library, but a more iterator-centric interface makes this property a little less intuitive. Third, there are now three permission levels instead of two. An iterator that can change element values and add or remove elements, an iterator that can only change element values, and an iterator that cannot do either. I've only implemented the full and zero permission iterators.

Templated Algorithms

Next, I needed to combine the first and last iterator into a single input. I started by creating templated algorithm definitions in algorithm.h, search.h, sort.h, and filter.h that accept take a whole container as input. Now our code is looking much cleaner.

z = unique(sort_quick(x));

Generic Slices

The algorithm implementations are clean enough, but I also needed a way to call those algorithms on parts of a container as in the Standard C++ Library. I needed a range container so that I could work with a range of iterators. However, calling sort on a range of iterators tries to sort the range by comparing the iterators which is not the goal.

Enter generic slices. A slice wraps a container of iterators providing a direct container-like iterface to the iterated values. For example, I can now have slice<range<array<int>::iterator> > that implements the more prototypical slice or slice<list<array<int>::iterator> > that implements a generic selection of elements in an array using a list as intermediate storage of the iterators. If I call sort on one of these containers, it calls swap from and compares the values pointed to by the internal array<int>::iterator.

With a little bit of template magic, these slices can be made to function correctly with pointers as well as iterators. Now I can wrap a static array and treat it as a container. For example, a C string can be wrapped like this:

slice<range<char*> >(range<char*>(cstr, cstr+strlen(cstr)))

However, we still have a usability problem because I now have to type this monstrosity out every time I want to work with a slice.

slice<range<array<int>::iterator> >(range<array::iterator>(x.begin(), x.end()));

Little Helpers

To fix this, I need some helper functions. First, there is a series of sub functions in both the iterators and the main container class which returns a slice<range<iterator> >. For a container c and iterator i:

  • i.sub(int length) returns the sub range [i, i+length).
  • i.sub() returns the sub range [i, c.end()).
  • c.sub(int start, int end) returns the sub range [c.begin()+start, c.begin()+end).
  • c.sub(int start) returns the sub range [c.begin()+start, c.end()).
  • c.sub() returns the whole container in a range [c.begin(), c.end()).

Second, there is a sample function in the main container class that use a container of values to as indexes into another container. This allows me to create generic slices without going back to the slice constructor. The only time I do need to type out the slice template is when I declare one because I want to keep it around for later. An example usage of sample:

array<float> x = array_t(5, 3.5f, 2.2f, 9.5f, 3.0f, 2.5f);
cout << array_t(3, 0, 4, 2).sample(x) << endl;
// {3.5, 2.5, 9.5}

Finally, for convenience I created two further functions. deref wraps a container of iterators with a slice interface and ref strips the slice interface from a slice leaving the underlying container of iterators.

The Pet Peeve

Now we have solved everything but the pet peeve. The best solution would simply use an interface (as exists in Go) to define the comparison functions. However, C++ doesn't have that kind of interface. So, we are left with three possible solves. The first is to create a header file that includes every container header and creates pairwise comparison operators for those containers. However, this bloats your code by forcing you to include every container header and breaks down as soon as you add a new container. The second method is to create a templated comparison function, but there isn't a good mechanism in C++ to ensure that it doesn't conflict with other comparison operators. The method I implemented uses an abstract base class which is the closest equivalent to interfaces in C++.

So, I created an abstract base class for all containers. However, because each container defines its own iterator classes, I had to template this base class against those differing iterator class definitions. This makes container definitions a little bit ugly.

template <typename value_type>
struct array : container<value_type, array_iterator<value_type>, array_const_iterator<value_type> >

However, it also allows me to define templated functions that can only be applied to containers. Any new containers I define will automatically work with these functions, and I don't need to include a giant header.

template<typename v0, typename i0, typename ci0, typename v1, typename i1, typename ci1>
int compare(const container<v0, i0, ci0> &a, const container<v1, i1, ci1> &b)
	ci0 i = a.begin();
	ci1 j = b.begin();
	for (; i && j; i++, j++)
		if (*i < *j)
			return -1;
		else if (*j < *i)
			return 1;
	if (j)
		return -1;
	else if (i)
		return 1;
		return 0;
Read More

Toward Better Representational Systems

The Current System

There are three branches in the United States Federal Government. The Legislative Branch is responsible for composing and maintaining the laws of the land, the Executive Branch is responsible for ensuring the laws are followed, and the Judicial Branch is responsible for interpreting and applying the law. All three branches are must perserve, protect, and defend the Constitution.

Legislative Branch

In the Federal Legislature, the House of Representatives is charged with representing the will of the People and the Senate with representing the will of the States. In practical terms, this responsibility is implemented with differing allocations and selection methods for representatives versus senators.

In the House, each state is alotted a number of representatives relatively proportional to it's population determined by a per decade census. The total number of representatives in the House is currently fixed at 435 and each state is given at least one representative. Representatives are re-elected every two years, far more often than the senators, so that they are more in touch with the contemporary views of the People. Selecting these representatives is up to each individual state. In many cases, the state is divided into nearly equally populated districts that are each given a single vote. The people in each district vote to determine how the district as a whole should vote, generally using a First Past the Post voting system. Furthermore, ballot access is typically limited to only a small number of political parties.

In contrast, each state is alotted exactly two senators who are re-elected every six years. The method of selecting these senators has been left to the individual state. Some appoint their senators through a vote from their state legislative body while others elect their senators through a popular vote. Again, ballot access is typically limited to the main political parties.

Executive Branch

The President stands as the top-most authority in the Executive Branch, commanding the military, police, intelligence agencies, diplomats, postal workers, and a host of other federal agencies. The President and Vice-President are elected as a team by the Electoral College in a First Past the Post vote. After which they appoint the rest of the administration.

The Electoral College is group of electors about equal to the number of representatives (435) plus the number of senators (100). Each state is alotted a number of electors relatively proportional to it's population and selecting these electors is left up to each individual state. Typically, cadidates are nominated by each political party then selected using a popular vote First Past the Post election. In 48 states, the winning party gets all of the elector slots.

How the Electoral College Works

Judicial Branch

The Judicial Branch is a hierarchy of 94 district courts, 13 courts of appeals, and the Supreme Court at the top. The Supreme Court hears cases to determine not whether someone is guilty of breaking a law, but whether the law is in line with the Constitution. The judges of these courts are appointed by the Executive Branch.

Systemic Failures

Campaign Funding

In 2010, the Citizens United v. FEC ruled that corporations corporations are people and money is speech. This opened the flood gates to corporate campaign contributions and lobbying causing significant economic inequality.

Corruption is Legal in America

First Past the Post Voting System


The First Past the Post voting system is tearing our country apart. A study of the 2012 French election against different voting systems showed that First Past the Post rewarded polarizing candidates.

Baujard, Antoinette, et al. Who's favored by evaluative voting? An experiment conducted during the 2012 French presidential election. Electoral Studies 34 (2014): 131-145.

But its not enough to just look at the 2012 French elections. Every year, political discussions in the United States get more bitter, resentful, hateful, and aggressive. According to a study from 1994 to 2014 by the Pew Research Center, candidates are elected further toward the extremes of their party every election.

Political Polarization in the American Public

And if that's not enough, xkcd did a full study throughout all of the United State's history. You'll notice that in 1932, a majority of the candidates were center left or center right whereas now most are far left or far right. There are political upheavals that disrupt this trend before 1932, but it always starts over.

xkcd: The United States Congress: Partisan Ideological Makeup

Tactical Voting and the Spoiler Effect

In First Past the Post, you end up voting against the candidates you don't want instead of for the candidates you want. In the first election, there is no voting history, so everyone votes for the candidate that best represents them and the election is fair. But in subsequent elections, voters are driven away from the unsuccessful candidates that best represent them and toward more successful candidates that don't represent them as well. Over time, the system decays into just two parties.

The Problems with First Past the Post Voting Explained

Echo-Chambers and Filter Bubbles

Every online tool has to filter information in some way. Users have yet to really be able to control how that information gets filtered. The result is that these tools try to show us what it thinks we want to see by what we click on first. This means that we are no longer challenged by opposing points of view and many of us are more cut off from the world than before.

Beware of Online Filter Bubbles
TED Talks, Eli Pariser

Electoral College

The apportionment of electors to the states empowers the people in some states while inhibiting those of others. States like Texas, California, Florida, and New York have about 700,000 people per elector whereas Wyoming, Vermont, Alaska have only 200,000 people per elector. This means that people in Wyoming, Vermont and Alaska have 3.5 times the voting power as people in Texas, California, Florida, and New York.

Data from and pewforum.

This ultimately makes it possible to win the presidential election earning half of the electors while having 22% of the popular vote.

The Trouble with the Electoral College

Structure of Legislative Branch and Representative Apportionment

The Senate is supposed to represent the Will of the States and the House of Representatives is supposed to represent the Will of the People. However, neither really serve those functions. It would be more accurate to say that they both represent the will of the majority in each state. The difference is that the Senate gives equal voting power between states while the House weights a state's voting power by its population.

The primary assumption behind this structure is that people in the same geography will always have the same wants and desires and face the same problems and people in different geographies will always have different wants and desires and face different problems. Realistically, this assumption is faulty.

There are many factors that could cause two people to share wants, desires, and problems. They could belong to the same economic class or race, live or grow up in the same area, belong the same philosophy or religion, work the same job, share the same sexuality, have similar genetics, talk with eachother online, or share some other feature not in this list. Further, they could each have friends or loved ones that share one or more of these features. These same factors could also make them different. So the assumption that geography is the sole determiner for wants, desires, and problems is a faulty one.

Even if geography where a sole determiner of these things, an enormously inequal share of the voting power pie is given out to an extremely small percentage of the population. The same problem seen in the Electoral College is also is reflected in the House of Representatives where it is possible to elect a controlling interest with 25% of the popular vote. The Senate, on the other hand, is just absurd, requiring only 9% of the popular vote for a controlling interest.

Data from wikipedia and pewforum.

Data from wikipedia and pewforum.


The way districts are drawn has a significant effect on the outcome of the presidential election and the elections for the House of Representatives. Furthermore, these districts are drawn by the currently elected party in order to extract the most benefit.

Gerrymandering Explained

A Proposal

Many of these problematic systems are enshrined in the Constitution which means that making any changes would require a Constitutional Convention. However, it is getting clearer every year that changes must be made as the United States falls further and further in international rankings. I propose the following adjustments to get us back on track.

Corporations are not People

There are already several movements to get a constitutional amendment to reverse the decision of Citizens United. Some are listed below.

Campaign Vouchers

The Campaign Voucher program allocates some public funds for campaign contributions. Each person is sent a certain amount as a voucher which they can donate to campaigns as they see fit. Making this program exclusive, meaning the only way to donate to a campaign, would solve many of the inequality problems regarding campaign contributions.

For an example of a non-exclusive Campaign Voucher Program in action, see Seattle's Democracy Voucher Program.

Approval Voting

The Approval vote ballot looks the same as a ballot for First Past the Post. However, instead of voting for only one candidate people can mark as many candidates as they like. The votes are all added together and the candidate with the most votes wins. This minute change makes all of the difference.

The study of the 2012 French election found that the Approval voting system rewards unifying candidates. This means that discussing politics will no longer be a cultural faux pas. The hate and frustration associated with politics will dwindle and we can get back to being reasonable.

Also, it is impossible to vote tactically. There are no forces pushing people to vote against their own best interests. This means that we can have choice at the voting booth once again.

Why not Instant Runoff?

A more commonly expressed alternative is Instant Runoff. While Instant Runoff does solve the Spoiler Effect, it ultimately fails to eliminate tactical voting and still decays into a two party system.

Why not Range Voting?

Another expressed alternative is Ranged vote. Approval voting is a type of Ranged vote system where the range is either 0 or 1. The main problem with the Ranged vote is that it fails to eliminate tactical voting. In order to increase their changes of their candidate getting elected people will tend toward the extremes of the range. Eventually, the Ranged vote ultimately collapses into an Approval voting system so the damage is minimized, but why deal with that in the first place?

National Popular Vote

The hierarchical election systems were designed at a time when communication with different districts meant riding on horseback for a month. It made sense to send a single representative who would vote for you instead of expecting them to remember the number of people who voted for each candidate. However, in the modern age, communication is instantaneous and these institutions only serve to increase representative inequality among the population. It is necessary to replace all of these hierarchical systems with flat popular votes.

Idealogical Representation and Balance

I would like to introduce a few alternative legislative systems that share several basic tenets.

The first is that we want to avoid both tyranny of the majority and tyranny of the minority. The basic structure that I will lay out is designed to allow both the majority and minority to check the other and balance eachother out.

The second is that state boundaries have no place in the Federal Government. The process of determining legislation should not be a battle between arbitrary geographical boundaries. A geographical partitioning only serves to empower some while disenfranchising others.

Idealogical Representation

This is where Idealogical Representation comes in. Instead of representatives being allocated to states, they are allocated to idealogies and state boundaries no longer play a role. During the election, the ballots are handled as usual. People would vote in an Approval voting system and we would tally up all of the votes in a flat vote across the nation for all candidates.

First, the candidate with the most votes is selected and given a seat. Then, the people who voted for that candidate are removed the the voting pool because they now have a representative. Then, the votes in the voting pool are re-tallied and the next majority winner is selected. This proceeds until a specified number of candidates have been chosen.

Functionally, this gives the majority one representative, the next biggest minority one representative, the next biggest one representative and so on until all of the seats are filled. The more available seats there are, the more minorities are given representation and the more variety there is in that representation.

There are many possible ways to modify this election method. Instead of removing the voters from the pool entirely, multiply their vote by a fraction to reduce their voting power. Or once elected, weight representative voting power by the number of people that support them. Or, instead of selecting just one, use Proportional Representation.

Single-House Structure

Instead of a two-house structure, just have a single legislative branch that uses Proportional Idealogical Representation. This would balance the voting power of all idealogical groups by the number of people in each group. A group of minorities could over-rule the majority by forming a coalition.

Minority and Majority House

The Minority House will use a flat Idealogical Representation, giving power of that house to the minority idealogies. The Majority House will run a national Approval Vote and just select all of its candidates from the top of the list giving power of that house to the majority. In this system, no coalition of minorities could over-rule the majority. Instead, both the minorities and majority would have to agree on every law.

Determining Law Jurisdiction

The concept of a state is not a useless one. Today, states represent a structural solution for effectively governing people across a wide expanse of different geographies. However, one of the primary problems with this kind of hierarchical governance structure is how to determine which level of governance should solve particular problems. Where does the jurisdiction of the Federal Legislature end and the jurisdiction of the State Legislature begin? Theoretically, this was solved by giving each state representation as an entity in the Federal Legislature. Though ultimately, this structure tends toward moving power up the ladder and into the national ball park.

At the moment, there is no well-structured mechanism for determining at what level of government something should be discussed. I propose that when 66% or more of the lower level entities sign a law saying a specific issue should be discussed at a higher level of government, then that issue moves up the ladder. If an issue is already a national issue, then if less than 50% of the lower level still have such a law in place, the issue gets sent back down the ladder. This uses hysteresis to ensure stability in government programs while still allowing lower government entities to retain power.


Ultimately, there are a lot of issues with the structure of our government. However, I believe that I have highlighted some of the more important ones in today's political climate.

Read More

Computing Trends

After recently giving a presentation as part of my PhD, I am left with a large swath of data. This is data that, to anyone in the field, is not particularly surprising, but is also damn impossible to find. To anyone not studying Computer Architecture, you might find these trends interesting.

The first thing to cover is Moores Law which is a self enforced trend in which the number of transistors on die (the bit of silicon inside a computer processor package) doubles every four years. Most of the following data comes from CPU DB by Stanford's VLSI group. Keep in mind that the following are log plots which is why the trends look linear.

Transistors on Die

From the formation of the industry until about 2005, this also mapped to an increase in performance. In 2005, the industry encountered three different barriers.


The first barrier is known as the Power Wall. Before 2005, the primary driver of the performance trend was frequency scaling. As the number of transistors on die increase, they also got smaller giving them a higher maximum switching frequency. The increase in switching frequency of the whole chip accounted for equivalent increases in performance.

Clock Frequency

However, as frequency scaled up, so did power until the chip was producing more heat than a fan-cooled heat sink could disperse. As a chip heats up, the maximum switching frequency of the transistors on die slows down. Heat also adds wear and tear by exacerbating electromigration. Effectively, electrons in a wire pick up gold atoms from one place and drop them at another much like water erodes away rocks in a river. So to increase the frequency further, we would have to switch to some other cooling medium like water which is ultimately uneconomic. Also, the formation of the mobile market with the introduction of the iPhone in 2007 dramatically increased the demand for low power processing devices.

Processor Power

So, to keep scaling performance while maintaining frequency and therefore power, the industry turned to parallelism, increasing the number of cores on die and the number of assembly instructions each core could schedule per clock cycle (instruction level parallelism). The ILP graph data is from Wikipedia's Instructions Per Second page.

Core Count

Instruction Level Parallelism

However, according to Amdahl's Law, the speedup attainable from parallelism is dependant upon the type of workload. If the workload isn't parallelizable, then this doesn't help. Also, there is an asymptotic upper bound for the attainable speedup for any workload dependant upon the smallest sequential action in that workload. Ultimately, this is called the ILP Wall. Jyotsna Sabarinathan at the University of Texas did a study of available parallelism in a few workloads in 1999.

Attainable Speedup for Parallel Workloads

The third barrier is called the Memory Wall. The throughput of memory systems are increasing at a much slower rate than the throughput for computing systems. This is creating a bottleneck between the memory hierarchy and the computing fabric that slows the whole system. This data comes from the Stream Benchmark by John D. McCalpin.

Memory vs Compute Throughput

Read More

Paradigm Shift

Political Activism seems to be stuck in an era before instant and ubiquitous communication. Every party organizes geographically, dividing the nation into districts. The party assigns a chair to manage each district and garner funding, votes, and support. It then uses a deep hierarchy to manage the county, state, and national constituent bodies.

This organizational structure separates the party control from the constituents it represents. They only have direct access to the district chairs who are elected every four years. The district chairs elect the county chairs and so on. At each higher level, you need to influence fewer people to affect meaningful change. However, you also need more money and status to influence those people. This creates ample opportunity for those with money and status to affect meaningful change while stifling the opportunity of those without. The structure is also quicker to respond to those with money and status because they can influence higher in the hierarchy. So while it takes years of constant effort for a large group of constituents to change the party politic, it takes a weekend for the large donors to overthrow that effort.

The Millennial Generation marks a significant shift in ideological paradigm and social structure, driven by instant, ubiquitous, and expansive communication technology. The social interactions of previous generations were geographically limited making them more likely to exchange ideas with their neighbors than their friends further away. Meanwhile, Millennials interact across vast networks and are more likely to exchange ideas across further distances. Our political system as a whole is geared toward geographic clustering and hierarchical organizational structures. These effectively stifle the voice of the newer generations and amplify that of the older. This is causing newer generations to quickly lose trust in our political institutions as exposed by the voter turnout of the last three elections.

However, I posit that given the right organizational tools, newer generations will have a distinct advantage to rid themselves of the corruptible hierarchical structures that plague our political sphere. A glimmer of this advantage was seen surrounding the introduction of causing a peak voter turnout in 2008. If a political organization were to create an online democratic platform that gives power to its supporters, they could garner virulent support from modern voter blocks.

If we examine current political organizations like The Democratic Party, The Republican Party, The Green Party, The Libertarian Party, Brand New Congress, Swing Left, Our Revolution, and The Tea Party, it becomes apparent that they are either unaware or are unwilling to give up control of their organization. On each website, they ask for an email address and phone number and throw you a few petitions to sign. The leaders and political candidates are inaccessible, discussion is non-existent, organizational structure and goals are unpublished, the platform is unmoving, and the funding is mysterious. This creates a unique opportunity for the first political organization that encourages true online participation.

Read More