Profile

Cover photo
Jason Schulz
35,876 views
AboutPostsPhotos

Stream

Jason Schulz

Shared publicly  - 
 
A simple prime sieve.  It uses a bitset to represent the integer range sans even values.  So, the function that maps from bit index to value is...

f(x) = 2x + 1

The seemingly bizarre (3 *p) + 1 just multiplies the actual value by 3, and (2 * p) + 1 similarly multiplies the value by 2.

size_t n = std::strtoull(argv[1], NULL, 10);

boost::dynamic_bitset<> cs((n + 1) / 2);

cs.set();
cs.set(0, false);

for (size_t p = 1; p != cs.npos; p = cs.find_next(p))
  for (size_t c = (3 * p) + 1; c < cs.size(); c += (2 * p) + 1)
    cs.set(c, false);

std::cout << cs.count() + 1 << std::endl;

It's space efficient and reasonably fast.  At first glance both clang and gcc don't seem to optimize the bitscans into bsf, which I don't fully understand though.
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
The Supreme Court’s refusal to review the Federal Circuit’s dangerous decision in Oracle v. Google means that court’s decision will stand for now.
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
I implemented a few commands a while ago while I was re-building my laptop.  I thought they might be useful for other people, so I ended up re-writing them in a different language (python) and turning it into a package.

They do fairly basic things like make (copy) backups of files, undo the backup, swap two files, pivot files over commands (filter through awk, etc...)  I generally wrote them just to reduce the number of commands (amount of text) I had to type to do common things I do re-building a linux install.

I actually wrote them in bash first just to have something quick to use (the original scripts are still somewhere on github), but I ended up using them on almost a daily basis since.  So, I thought I'd try to make something other people might be able to use.

I built a source distribution and uploaded it to PyPI, so it should be easy to install.  The package is also MIT licensed, so if anyone wants to do anything with them, you should be able to.

Feedback is welcome.
sh-helpers - shell helpers
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
Somewhat interesting, Clang apparently compiles a generic byte swap into a bswap for x86.  I know at least a couple compilers can pick up on some bit manipulation patterns, but bswap is at least new for me.  Philosophical arguments aside, since '08 it bothered me there needed to be tradeoffs between hardware compatibility, maintenance effort, and performance for byte swapping.  The code for size_t is below.


for (size_t i = 0; i < sizeof(size_t) >> 1; i++) {
 
  size_t d = sizeof(size_t) - i - 1;

  size_t mh = ((size_t) 0xff) << (d << 3);
  size_t ml = ((size_t) 0xff) << (i << 3);

  size_t h = x & mh;
  size_t l = x & ml;

   size_t t = (l << ((d - i) << 3)) | (h >> ((d - i) << 3));

   x = t | (x & ~(mh | ml));
}

return x;
1
John Regehr's profile photo
 
It'll also compile (x<<c)|(x>>(32-c)) into a rotate left instruction.
Add a comment...

Jason Schulz

Shared publicly  - 
 
For anyone interested in distributed systems, or systems design in general...

I agree with the overall sentiment, but I personally disagree on subtle detail.  I don't think it's an attempt to justify designing limitations as a goal, however I think the point should be made that there is a difference between actual infinity and practical infinity.  IPv6 is probably the quintessential example, having addresses of 128 bits that support well over a billion addresses for every living human being on the planet (cats, dogs, etc...).  64 bits could also accommodate the same number, although natural resource limitations are not always the only concern worth considering.

There is also the point that sometimes there aren't natural limits, or taking the time to understand them is prohibitive, or on occasion there shouldn't be a limitation (arbitrary math, etc...); sometimes, not always.  I can name a number of projects off the top of my head that designed reasonable limits and ran into the designed limitations long before anyone expected with negative results (some worse than others). Communications protocols are the easiest example.  At very least, reasonable things should be designed to happen when any limits are encountered, which is obviously mentioned.    I can also name projects that were relevant over more than a decade, but they are drastically fewer and further between.
About Me. My name is Marc Brooker. I've been writing code, reading code, and living vicariously through computers for as long as I can remember. I like to build things that work. I also dabble in brewing, cooking and skiing. I'm currently an engineer at Amazon Web Services (AWS) in Seattle, ...
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
Nice summary of SFINAE.
There's an interesting issue one has to consider when mixing function overloading with templates in C++. The problem with templates is that they are usually overly inclusive, and when mixed with overloading, the result may be surprising: void foo(unsigned i) { std::cout << "unsigned " << i ...
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
Some interesting lecture notes on java internals.

I don't use switch(String) for performance critical code, but along with a couple other things, the implementation seems like it's dropping some on the floor.

Hashing is linear with respect to length; comparing generally as well.  Also, hash values are most likely sparse to the table, which means it likely doesn't compile to jump (lookupswitch).

It seems like a more efficient method would be using the length to map into an initial table.  Being less sparse, it's more likely to be compiled to a jump.  Mapping collisions could be handled with a radix or a binary structure, and any remaining ambiguous characters could be compared in a parameterized way (sans length).

Off the cuff, it seems generally the approach would be lower complexity, and allow more efficient hardware use.

Thoughts?
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
15:44:52         @jason| favorite ********
15:44:52          @root| Unknown command: favorite
15:45:00         @jason| favourite ********
15:45:01          @root| Command processed successfully
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
The protocol definitely looks like a work in progress, but it's an interesting approach.  GitLab might be another, but it solves slightly different problems.

Trust and consensus are pretty non-trivial to solve.  Maybe there are more pragmatic or generic approaches specifically for git repositories?
(This post is an aspirational transcript of the talk I gave to the Data Terra Nemo conference in May 2015. If you'd like to watch the less eloquent version of the same talk that I actually gave, the video should be available soon!) I've been working on building a decentralized GitHub, ...
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
The paper is an interesting read.  I've actually noticed Javascript libraries being one of the bigger bottlenecks for page load times before.  Analytics seem to be a big use, but one of the other major uses seems to be actual page formatting.  More pages adjust fonts and layouts dynamically.

Even with typesetting, MathJax superseded MathML, and Google prettify is generally de-facto for code sharing sites.  I used to pre-render to png files to avoid some of the complexity.
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
If you use vi(m) this might be interesting.  It's similar to pentadactyl/vimperator textareas, but it uses a vim instance in client mode which gives access to mappings, plugins, macros, etc...
pterosaur - All firefox text fields are vim.
1
Add a comment...

Jason Schulz

Shared publicly  - 
 
Latest Comments. - "It's rare to see this kind of hubris in a computer publication....." You're Doing It Wrong; - "BGPSEC won't solve the problems given here -- it doesn't actual...." Why Is It Taking So Long to Secure Internet Routing? - "I personally prefer J, because it is licensed under the ...
1
Add a comment...