2.373

Scott Aaronson writes:

For twenty years, the fastest known algorithm to multiply two n-by-n matrices, due to Coppersmith and Winograd, took a leisurely O(n^2.376) steps.   Last year, though, buried deep in his PhD thesis where hardly anyone saw it, Andy Stothers discussed an improvement to O(n^2.374) steps.  And today,  Virginia Vassilevska Williams of Berkeley and Stanford, released a breakthrough paper that improves the matrix-multiplication time to a lightning-fast O(n^2.373) steps.

...The world will not be the same!

C++11 N2765: user-defined literals

C++11 will have tons of new features and concepts. One among them is
N2765: user-defined literals (scheduled for GCC 4.7). Quite possible I'm dumb
and ugly, but frankly, "user-defined literals" is something I've so many doubts
about. There're already lots of examples, though I haven't seen anything really
neat so far (only speaking for myself).


For example:

constexpr long double operator"" _degrees (long double d)
{
        return d * 0.0175;
}

long double pi = 180_degrees;

Or (link)

typedef std::map MyMap;
MyMap create_map()
{
    MyMap m;
    m["lol"] = 7;
    return m;
}

auto m = create_map();

int& operator "" m(const char *key, size_t length)
{
        return m[key];
}

int main(void)
{
    std::cout << "lol"m << std::endl;
    // 7
    "lol"m = 2;
    std::cout << "lol"m << std::endl;
    // 2
    return 0;
}


Or (link)

template struct __checkbits
{
    static const bool valid = false;
};

template struct __checkbits
{
    static const bool valid = (High == '0' || High == '1')
                   && __checkbits::valid;
};

template struct __checkbits
{
    static const bool valid = (High == '0' || High == '1');
};

template
  inline constexpr std::bitset
  operator"" _bits() noexcept
{
    static_assert(__checkbits::valid, "invalid digit in binary string");
    return std::bitset((char []){Bits..., '\0'});
}

int main()
{
  auto bits = 010101010101010101010101010101010101010101_bits;
  std::cout << bits << std::endl;
  std::cout << "size = " << bits.size() << std::endl;
  std::cout << "count = " << bits.count() << std::endl;
  std::cout << "value = " << bits.to_ullong() << std::endl;

  //  This triggers the static_assert at compile time.
  auto badbits = 21010101010101010101010101010101010101_bits;

  //  This throws at run time.
  std::bitset<64> badbits2("21010101010101010101010110101010101_bits");
}


-ss

GCC 4.7.0: transactional memory

Eventually GCC 4.7.0 will have transactional memory, which has been
merged several days ago. Draft of still-in-progress design document can
be found here.

In short, (atomic) transaction is something similar to this:

    __transaction_atomic { x++; }

Any operation performed within the __transaction_atomic block will be atomic and
isolated from other transactions, operations within __transaction {} either be visible to other threads in its entirety or not at all.

Quote from lwn

Details on the specific implementation are scarce; it appears that, in the current patch set,
transactions will be implemented using a global lock. GCC developers debated for a bit over
whether this code was ready for merging or not. In the end, though, the possibility of being
the first to support an interesting new feature seemed to win out. Current plans are to
release 4.7.0 sometime around next April.

Refer to gcc.gnu.org (or gcc 4.7 svn repository) for details.

Prettiness of git hooks

Haven't blogged for a while, so just to keep this blog alive, some easy reading.
Recently due to project needs we had to organize external .git repository mirror for
code drops. The below notes probably will not discover anything new to you, though
still may be interesting. Just in case.

Well, to start with, we have several developer's trees and one master tree (obviously
for merging, pushing and keeping stuff(tm)). We also have to perform regular code drops
(say, several times a week) with .git directory included. The usual solution could be
just to perform `clone, pull, pull,...' on the remote machine, which, however, didn't
work for us because of some company policies.

So I performed trivial scp of cloned master tree to the remote machine (which is possibly
not the best thing to do, but I didn't feel like doing all that git init, scp files,
git add, git commit with "Initial commit" message, etc.), and cleaned up .git/config.

For scp-ed repo we should perform:
git config --bool core.bare true
otherwise an attempt to push will make git suspicious that you may accidentally screw
things up:
remote: error: refusing to update checked out branch: refs/heads/master
remote: error: By default, updating the current branch in a non-bare repository
remote: error: is denied, because it will make the index and work tree inconsistent
remote: error: with what you pushed, and will require 'git reset --hard' to match
remote: error: the work tree to HEAD.
remote: error:
remote: error: You can set 'receive.denyCurrentBranch' configuration variable to
remote: error: 'ignore' or 'warn' in the remote repository to allow pushing into
remote: error: its current branch; however, this is not recommended unless you
remote: error: arranged to update its work tree to match what you pushed in some
remote: error: other way.
remote: error:
remote: error: To squelch this message and still keep the default behaviour, set
remote: error: 'receive.denyCurrentBranch' configuration variable to 'refuse'.

The thing is that on the remote side we have to create --tag each time we perform
a code drop. And this is kind of error prone because it's so easy just to forget
perform git tag..., git push --tags.

So I created an alias for tagging on the remote machine

.git/config
[alias]
        datetag = !git tag "project_name_"`date +%Y%m%d%H%M`

(or perhaps time zone aware one via `TZ='REGION/CITY' date +%Y%m%d%H%M`).


The next thing was tagging automation. Which was simply achieved by
git hooks (git book). There are lots of them (you can find examples within
.git/hooks/ directory). In order to enable hook, just remove .sample at the end
of file name.

The ideal candidate was:
post-receive
GIT_DIR/hooks/post-receive
This hook is invoked by 'git-receive-pack' on the remote repository, which happens when a
'git-push' is done on a local repository. It executes on the remote repository once after
all the refs have been updated.


With somewhat trivial implementation:
.git/hooks/post-receive
#!/bin/sh
#
# To enable this hook, rename this file to "post-update".

exec git datetag



Since hooks are shell scripts it's really almost up to you to decide
the level of `complexity' and `sophistication'.


On the local host I created addition 'remote' config
.git/config
[remote "drop"]
        url = git@remote_host_name:/project_repository_path

and set appropriate ssh IdentityFile for Host in ~/.ssh/config file.

So now I can perform
1) git push
for pushing to local master

2) git push drop
for pushing and tagging to the remote host


That's it, git is really awesome.

-ss