This also supports `safe' explicit release which may be required in some circumstances where the gc is not run often enough.
It should work well with the JVM as it uses reference queues and no finalize methods. It requires minimal "extra" application support - just a class specific release() method.
The following few lines is now the complete makefile for dez. This supports `jar' (normal build target), `sources' (ide source jar), `javadoc' (ide javadoc jar), dist (complete rebuildable source), and now even `test' or `check' (unit and integration tests via JUnit 4) targets. The stuff included from java.make is reusable and is under 200 lines once you exclude voluminous comments and documentation.
java_PROGRAMS = dez dez_VERSION=-1 dez_JAVA_SOURCES_DIRS=src dez_TEST_JAVA_SOURCES_DIRS=test DIST_NAME=dez DIST_VERSION=-1.3 DIST_EXTRA=COPYING.AGPL3 README Makefile include java.make
The article is over on my home page at Using GNU Make for java under my software articles section.
This morning I wrote and published article about writing an image container class for Java which supports efficient use of Streams. It is on my local home page under Pixels - Java Images, Streams.
Although there is much said of it, there is still quite a bit unsaid about how many wrong-footed experiments it took to accomplish the seemingly obvious final result. The code itself is now (or will be) part of an unpublished library I apparently started writing just over 12 months ago for reasons I can no longer recall. It doesn't have enough guts to make publishing it worthwhile as yet.
I'm also still playing with fft code and toying with some human-computer-interaction ideas.
Just for something a bit different this morning I had an idea to do a record of developing software from the point of view of a "live blog". I was somewhat inspired by a recent video I saw of Media Molecules where they were editing shader routines for their outstandingly impressive new game "Dreams" on a live video stream.
Obviously I didn't quite do that but I did have a hypothesis to test and ended up with a working implementation to test that hypothesis, and recorded the details of the ups and downs as I went.
Did I get a positive or negative answer to my question?
To get the answer to that question and to get an insight into the daily life of one cranky developer, go have a read yourself.
I had comments open+moderated for a few weeks but got hit by spammers a couple of days ago so had to go back to id+moderated. Maybe something got lost in those 500 bits of snot but i don't think so. The spam was quite strange; most mentioned web sites but didn't provide links or weren't very readable so i'm not sure what the point was. Perhaps they're just fishing for open sites or naive moderators they can then exploit. Like the "windows computer department" that keeps calling and calling hoping i'll not tell them to fuck off every time (sigh, no i don't normally say that although i would tonight).
I've still got the subversion clones but i'm not inclined to do much with any of it for the forseeable future and i'm not even sure if i'm going to continue publishing other bits of code i play with going forward.
Desktop Java, OpenCL, ARM assembly language; these things are just not very common in the Free Software world. Server Java is pretty common but that's just, well, `open sauce' companies sharing costs and not hobbyists. So i think all i'm really doing is providing hints or solutions for some student's homework or help for graduate programmers to keep their jobs. And even then it's so niche it wouldn't be many, if any.
As an example of niche, I was looking up some way to communicate with adobe photoshop that doesn't involve psd format and one thing i came across was someone linking to one of my projects for some unfinished experiments with openraster format - on the first page of results. This happens rarely but still too often. Of course it could just be the search engine trying to be smart and tuning results to the user, which is a somewhat terrifying possibility (implications beyond these types searches of course). FWIW I came to the conclusion photoshop is just one of those proprietary relics from the past which intentionally refuses to support other formats so it's idiot users can continue to be arse-reamed by its inflated price.
As a hobby i have no desire to work on larger projects of my own or other established projects in my spare time. Occasionally i'll send in a patch to a project but if they want a bunch of fucking around then yeah, ... naah. In hindsight i somewhat regret how we did it on evolution but i think i've mentioned that before. Neither do i need to solicit work or build a portfolio or just gain experience.
I'm not sure how many hobbyists are around; anyone with remotely close to enough skill seems to be jumping into the wild casinos of app-stores or services and expecting to make billion$ and not just doing it for the fun of it. Some of those left over just seem to be arrogant egotistical fuckwits (and some would probably think the same of me). Same as it ever was I guess.
I suppose I will continue to code-drop even if it's just out of habit.
For another hobby I made kumquat marmalade on the weekend. Spent a couple of hours in the sun slicing the tiny fruit and extracting seeds (2-3 cups worth of seeds) and cooked it the next day. Unfortunately after all that effort it looks like it wasn't cooked quite enough and it probably wont set - it's a bit runny but at least it tastes good. Not sure what i'll do with 2-odd litres of the stuff though.
So I worked out what the mis-feature was actually called - it's called "show method parameters".
Then I downloaded the netbeans source code (all of it, i used a zip - netbeans-src, not sure if i could've just got the ide module, mercurial looked like it was going to take forever so i didn't bother).
I worked out where the offending bit of snot lived: "editor.completion"
I fixed it:
--- editor.completion/src/org/netbeans/modules/editor/completion/CompletionImpl.java~ 2014-11-18 19:07:58.000000000 +1030
+++ editor.completion/src/org/netbeans/modules/editor/completion/CompletionImpl.java 2015-05-02 22:39:20.935817693 +0930
@@ -1271,16 +1271,6 @@
* May be called from any thread but it will be rescheduled into AWT.
*/
public void showToolTip() {
- if (!SwingUtilities.isEventDispatchThread()) {
- // Re-call this method in AWT if necessary
- SwingUtilities.invokeLater(new ParamRunnable(ParamRunnable.SHOW_TOOL_TIP));
- return;
- }
-
- if (ensureActiveProviders()) {
- toolTipCancel();
- toolTipQuery();
- }
}
/**
And then after a few false starts trying to work out how to compile the module, I got it compiled. I put "cluser.config=ide" in nbbuild/user.build.properties and then ran 'ant jar' in the editor.completion directory. I'm not exactly sure what made it work in the end because things sort of failed and then they didn't. It refuses to build on jdk8 (as documented) but i had a jdk7 lying about already. It didn't take very long - i was genuinely impressed.
I found where the generated module went (nbbuild/netbeans/ide/modules/org-netbeans-modules-editor-completion.jar) and then copied that into both the system (/usr/local/netbeans-8.0/ide/modules/) and local (~/.netbeans/8.0/modules) module dir.
And then I started netbeans and checked to see if it took. So far looks ok.
It's a pretty strange feature to start with given it's functional overlap with code completion but it's a mystery why it is also turned on automatically every time you do any code completion or parameter lookup.
For starters the code completion window already shows this information - why pop up another less readable tooltip to duplicate it?
The other problem is that it shows the parameter lists for ALL functions of the same name not just the one specified by the current arguments (or even the type of the argument under the cursor). This just makes it a big mess with insufficient local context to make it readable at 'thinking speed'.
And the icing on the cake is that once you've 'done' your completion or parameter lookup task and moved the cursor - it decides it still wants to hang around a bit longer and jumps to the parameters of the function call you're inside of - i.e. if you're in an in-line lambda or a anonymous class definition it will move up to the function call that the lambda or new Thing is a parameter of. i.e. that code you already finished, perhaps months ago.
So ... out comes ESC. And again, and again. Almost EVERY TIME I use code completion. When i'm cutting lots of code this can be up to dozens of times in a given minute. Of course I type ctrl-space to initiate it that often too, but that's something I asked for and not some undecipherable clutter to piss off.
I already have all the popups and tooltips turned off and only call them up explicitly using ctrl-space; it got to the point there was so many little boxes flashing across the screen as i typed it was like standing around while flies keep landing on your face - once or twice is no big deal but constantly it becomes more than just a bit annoying. Swatting flies is a very apt description of using some ide's in their default configs.
But given it was so easy to build I may look at another annoying behaviour. The 'show matching parenthesis' function shows the matching parenthesis of any bracket the cursor is merely touching and gives no indication of which side of the bracket the cursor is on. This just makes it harder to work out where the cursor insertion point is when you're otherwise not interested in the matching bracket.
It could just be familiarity (although i only recently turned it on in emacs so it really isn't) or it's lisp implementation but the way emacs works makes it more useful. It will only highlight the matching bracket if the cursor is to the right of a close bracket or sitting on an open bracket (insertion point is to the left). If it's both, it will highlight the opening bracket of a close bracket since that's more useful. emacs uses a block cursor rather than a line which I also find easier to use for fixed-width character editors for a couple of reasons including that it goes hollow instead of vanishing when the window loses focus - which makes it easier to relocate if you're switching between windows on the same screen(s).
Some things I tried and discarded: incrementally chaining the hash table (avoiding the realloc+copy); inlining the hash function; calculating all hashes of source and target at the start; doing the same in parallel. Most of them amounted to no gain although the parallel hashing helped quite a bit in some cases but not often enough to be worth the memory required.
Thus this is mostly a post about the expanded homepage where i added a bit detail and more benchmarks.
I was a bit surprised with the memory use compared to the "competition" because dez amounts to a full exhaustive search, albeit index assisted, whereas the others do not.
Probably of no use to anybody but what the hell. Maybe one day i'll make some better sfx for that space invaders I did.
It's got it's own home page up on the usual spot.
A couple of nights ago I tried one of the hashtable ideas from a previous post. It made a big improvement so I kept whittling it away until there really wasn't much of a hash table left apart from a couple of arrays. Fastest version using the least memory. Open addressing just didn't handle some bad cases at all well.
I didn't see the point in keeping the others around so i only kept this one in the release.
And that should be me done with this for a while.
One goal was also efficient storage so I worked on a system which stored changes as reverse deltas. After some searching i came across the vcdiff format and some java code to work with it - but much of each implementation is pretty undecipherable code and to be honest just not that hot and I had a niggling interest to look a bit further into the problem.
So today I basically wrote my own from scratch and surprisingly it creates smaller diffs than jvcdiff given that it is literally an afternoons hacking and a naive approach at best (at least on a single example). Runtime is comparable although in either case they are very quick. I'm still trying to get hard statistics on memory use and gc load but i'm pretty sure it's better too.
I also looked at badiff which works with very large files, but that isn't something I need and it generated very fat diffs, used a ton of memory, and wasn't very fast (putting it lightly, see below).
Anyway the problem turned out to be quite interesting along the way.
It's more or less based on Bentley-McIlroy's paper `Data Compression Using Long Common Strings' although that paper is so brief I didn't get a great deal from it after a skim read. It's guts I think is more or less based on Rabin-Karp's paper `Efficient randomised pattern-matching algorithms' but that was too dense for weekend reading so after my eyes glazed over I did a quick scan of the wikipedia article and then thought about what problem it was actually solving.
In more human terms I think it basically devolves into this: compare every sub-string in the target array to every sub-string in the source array to identify the longest match. Use it to do shit. The details come in trying to make this practical and efficient and what `shit' you do with `it'.
So the following algorithm is kinda probably the same thing but only based on a loose understanding thereof.
# algorithm to generate a list of editing commands
# which transforms one array into another
hsize = length of sub-string
hstep = bytes to step in input
htable = hash table mapping hash value to location
# build hash table
for each location in source in steps of hstep
htable.addHash(source, location)
end
# find matches
for each location in target
hash = generateHash(target, location)
for each candidate in htable.lookup(hash)
determine longest actual match
of source @ candidate against target @ location
end
if there was a match and longest > threshold
if any data not matched
output an append command
endif
output copy command
location += match length
fi
end
add any left over
As one can see it's actually rather simple and mirrors the one-sentence English text description in a straightforward way. The hash table is only used as a helper to narrow the search space to possible candidates rather than having to check them all.
It requires the full source data but could trivially stream the target data. Restoring the target requires the source plus the list of editing commands.
hsize is typically 4-8 and determines the runtime and compression rate. A smaller number gives more potential candidates to match against (and more hashing clashes) but a larger hash will not match smaller strings.
hstep sets how often the source is sampled. Using a hstep of 1 gives the best result by far but results in a large hashtable and longer running time.
Rolling hashes are used so the hash length has no effect on that calculation but it does affect the runtime in other ways.
There are two interesting problems here - rolling hashes and the hash table itself.
I tried to implement a Rabin-Karp hash but lost patience trying to get my head around the modulo maths. I think i just had some indexing bug rather than mathematical ones but in the end I felt more comfortable with a cyclic hash based on rotating bit arithmetic. The mathematics are still messy but even the 6510 cpu has a 'ror' instruction and so the actual code is trivial for a digital computer.
// Copyright (C) 2015 Michael Zucchi
// License is GNU GPL v3 or later
public class CyclicHash {
int b;
int hash;
int fix0;
static final int[] random = new int[256];
static {
Random r = new Random();
for (int i = 0; i < random.length; i++)
random[i] = r.nextInt();
}
public CyclicHash(int b) {
this.b = b;
this.fix0 = ((b - 1) * 9) & 31;
}
public int init(byte[] data, int off) {
hash = 0;
for (int i = 0; i < b; i++)
hash = rotateLeft(hash, 9) ^ random[data[i + off] & 0xff];
return hash;
}
public int update(byte leave, byte enter) {
int leaving = rotateLeft(random[leave & 0xff], fix0);
int entering = random[enter & 0xff];
hash = rotateLeft(hash ^ leaving, 9) ^ entering;
return hash;
}
}
A random table is used to create the hash values for each possible byte. To add a new value to the hash it is first rotated and then xor'd with the random hash for the new byte. To remove an old value one only has to rotate by the length of the block and xor it again. Rotation is supposed to be modulo 32 but the java implementation in Integer is not and doesn't match the javadocs - to make sure I do it first (actually it worked before i did this so i know it works but this simplifies the call). The shift amount of 9 i plucked out of my arse.
Choosing better `random' values has some effect but this works.
I don't just want a simple hash table I want a hash table which lists all the potential match candidates against a given hash value. In java this could be expressed as:
HashMap<Integer,List<Integer>> htable;
However this will (should, i imagine) have scalability and gc issues and boxed primitives are quite heavy weight to start with.
There are some good optimised java libraries for primitive hash tables but i don't think they support multiple entries off the same hash key and they tend to be gigantic libraries targeted at different problems. Anyway it's the sort of problem i find interesting (fun, actually) so I came up with my own.
I sat outside in the last of the rays of the sun with knuth and a beer and read up on open addressing hash tables. Typically i'm partial to the chained variety for their conceptual simplicity but from looking at some libraries like trove it seems open addressing has benefits in some cases and particularly for java. Armed with the knowledge and the setting sun I came up with a space efficient 'approximate' hash table which suits the problem at hand.
// Copyright (C) 2015 Michael Zucchi
// License is GNU GPL v3 or later
class MatchMap {
int[] values;
int mask;
int logN;
static final int EMPTY = Integer.MAX_VALUE;
public MatchMap(int N) {
int size;
logN = 31 - Integer.numberOfLeadingZeros(N);
size = 1 << (logN + 2);
mask = size - 1;
values = new int[size];
Arrays.fill(values, EMPTY);
}
public void add(int hash, int value) {
int i = hash & mask;
int c = ((hash >> logN) | 1) & mask;
while (values[i] != EMPTY)
i = (i + c) & mask;
values[i] = value;
}
public void foreach(int hash, IntConsumer func) {
int i = hash & mask;
int c = ((hash >> logN) | 1) & mask;
int v;
while ((v = values[i]) != EMPTY) {
func.accept(v);
i = (i + c) & mask;
}
}
}
It uses open addressing with double hashing and doesn't bother with store the hash key, only the value. Knowing the size is important - but also known in this application. Deletes are a bit messy but fortunately not required. The table is sized so that the load factor is well less than 0.5.
Adding a new entry just starts probing at the modulo-size location and searches for an empty slot, stepping by the second hash (higher bits in the function or'd with 1 to make it odd). Knuth suggests using an odd number for the step which makes a lot of sense; it will eventually visit every location. This is an effective technique against clustering that occurs if linear probing is performed (I also tried that).
Retrieval just does the same thing. Any values are considered potential matches even if they were stored by a completely different hash key. Given that each location needs to be compared directly with the data arrays it doesn't make mistakes very costly and it even seems to improve the delta output in some cases.
One might note here ... this in total ... is probably less code than just the extra scaffolding required to use a java collections hashtable+list for the same purpose and probably 4-10x more space efficient. open-vcdiff has ~1KLOC for this purpose although that's about half comments explaining it's complexity - i don't even care to understand it enough to know if any of that is actually justified.
These two functions are 80% of the smarts and about 30% of the code. The rest is just to wrap it in some 'efficient' byte-streaming encoding, settle on a magic number, and write a decoder. vcdiff encoding would be nice but the encoding is a little more work than I have time left this weekend.
I created a delta from the text versions of GPL 2.0 to GPL 3.0 using this and compared to jvcdiff and badiff. As I said i don't think jvcdiff is the best implementation and it appears to just be a port of open-vcdiff, but it's what I have handy. For jvcdiff i'm forcing a single window but otherwise using the defaults.
badiff jvcdiff DEZ1
(6,1) (6,2) (6,4) (8,1) (8,8) (16,16)
source size 18092
target size 35147
patch size 47833 28829 18064 19053 20421 19128 23159 28877
encode 0.174870 0.002000 0.001550 0.001200 0.000950 0.001250 0.000720 0.001000
decode 0.000700 0.000170 0.000150 0.000150 0.000150 0.000120 0.000090 0.000060
hardware is kaveri cpu, jvm is oracle java 8 64-bit.
FWIW gzip is about 16K for both concatenated together, but that isn't really the same thing.
The value in brackets is (hsize,hstep). A larger hstep will reduce the size of the hash table generated and thus affect memory use, possibly significantly. hsize affects the minimum length of a match as well as hashing conflicts at the low end.
Times are in seconds and approx/rounded from the last few of 200 runs - jvcdiff has much more complex code so it takes nearly this many before it is fully optimised by the jvm, before that it is approximately 0.01s for encode. Because it's fast it might need even more loops for the jvm to notice. Due to randomisation of the hash in these test runs the DEZ1 encoding can vary between runs.
Dunno what's up with badiff, maybe this data isn't suitable for it and/or it's tuned to larger datasets.
As I said I don't have any hard data on the memory footprint but for DEZ1 the (x,1) worst-case it uses a 64K element int array for the hash table, plus the memory for the input and output buffers and half a dozen small utility objects. Decoding needs no extra memory apart from input, patch, and output buffer; and the output size is encoded in the delta so it only needs one allocation of non-garbage.
After writing most of this I tried the (16,16) option and considering the patch size is close to jvcdiff perhaps that matches the parameters it uses. Actually I kinda knew about this but forgot about it. Even then it is surprising that the delta size is about the same as jvcdiff uses much more advanced encoding techniques from VCDIFF that should reduce the size.
There's probably not much point going into a lot of detail in the file format but lets just say i chose the most compact and simplest format I could.
Integers are encoded using a big-endian stream of 7-bits data + 1 bit continue indicator, much the same as vcdiff and dozens of other binary encodings.
Because I only have two opcodes as a further optimisation I encode the opcode as a single bit along with the length. This allows lengths of up to 63 bytes (hmm, 64 if i add one ...) to be encoded together with the opcode in a single byte.
I just encode the copy source address as an integer every time which means they will tend to take 3-4 bytes in typical files. This is where a lot of the smarts in vcdiff comes from but it also requires more faffing about and runtime overheads.
So a relatively cheap and possibly significant improvement is to include the the incremental output as part of the search space: i.e. the part of the output which will have been decoded up until that time. As long as the hash table is big enough that should be relatively simple in the encoder and isn't much more work in the decoder.
I don't see the need for run-length encoding as it rarely comes up in real text (and yeah, real men use tabs).
Since the code is so simple it is open to gains from micro-optimisations. Being simple does help the compiler a lot to start with though and hotspot compiles faster code with less lead-time than the more complex implementations.
The hash table is a critical part of the performance and could be tuned further, not that there is much code to tune.
Currently any match of 4+ is encoded as a copy even if an add might be smaller. I don't know if 4 is even the best value. A look-ahead of a few characters may also yield longer matches and more compact encodings. Other address compression techniques as used in vcdiff could be used.
Scalability is unknown. My application is 'post-sized' text so it should be fine there. Increasing the block size (hsize) tends to speed up the encoder as it reduces the search space, but it misses small matches so the delta size increases. A two-tiered approach might work: a longer hash for the whole file and a smaller hash for a local region.
Having said all that, 'simplicity' and 'good enough' also have their own considerable charm and appeal so I might just clean it up and do some better testing and tuning and leave it at that.
Well ... I guess that was a fun afternoon, ... which seems to have gone well beyond midnight, oops - these long articles take hours to write. Given I went in blind i'm pretty surprised that the results are at least comparable to existing code with such modest effort.
I'm also surprised - or maybe not surprised if i let my ego talk - at how simple the algorithms actually are compared to the complexity of any implementation i've seen. And it's a little difficult to see this case as a matter of being a subject expert thus making it appear simpler than it really is. The Bentley/McIlroy paper mentions a working implementation in ~150LOC of C which was hard to believe looking at these libraries; but now i do.
And also ... back to work (later) today. It's been an indescribable 3 month break, but not as good as that sounds. I guess I lost 5 kilos in the last 6 weeks.
Once I do some testing and perhaps revisit the libCL linking mechanism I guess I'll do a 1.0, but given 0.3 was a year ago, ... yeah - don't hold your breath :)
I'll make a copy of all my projects and then delete them. Probably sooner rather than later (probably immediately because i'd rather get it out of the way, i have a script going now). I'm keeping all the commit history for now although i never find it particularly useful. Links in old posts may break.
Some of them may or may not appear later somewhere else, or they may just sit on my hdd until i forget about them and delete them by accident or otherwise.
Wherever they end end up though it wont be in one of the other commercial services because i'm not interested in doing this again.
I need to do the same to this blog, ... but that can wait.
Update: So ... it seems someone did notice. Don't worry i've got a full backup of everything. In part I was pissed off with google and in part I wanted to make it immediately obvious it was going away to see if anyone actually noticed. Who could know from the years of feedback i've never received.
If you are interested in particular projects then add a comment about them anywhere on this blog. All comments are moderated so they wont appear till i let them through but there is no need to post more than once (i'll delete any nonsense or spam unless it makes you look like a bit of a wanker). I will see about enabling anonymous comments for the moment if they are not already on. I can then decide what to do depending on the interest.
I will not be using github or sourceforge nor the like.
In a follow-up post i'll see where i'm going with them as well as pondering the future location and shape of the blog itself. I've already written some stuff to take the blogger atom stuff, strip out the posts, download images, and fix the urls.
(in resp to Peter below) I knew the writing was on the wall when google code removed binary hosting: it's kinda useless for it's purpose without it. This is why all my new projects subsequent to that date are hosted differently.
As usual it is available on the ezesdk home page.
It still requires root to run and i haven't looked at all into the "new driver" stuff. I've been keeping a pretty loose eye on that but not doing anything about it.
This is the final rasteriser (hardware) loop I ended up with. The scheduling might be able to be improved a tiny bit but I don't think it will make a material difference. This is performing the 3 edge-equation tests; interpolating, testing and updating the z-buffer; and storing the fragment location and interpolated 1/w value.
d8: 529f 1507 fsub r2,r44,r21 ; z-buffer depth test dc: 69ff 090a orr r3,r18,r19 ; v0 < 0 || v1 < 0 e0: 480f 4987 fadd r18,r18,r24 ; v0 += edge 0 x e4: 6e7f 010a orr r3,r3,r20 ; v0 < 0 || v1 < 0 || v2 < 0 e8: 6c8f 4987 fadd r19,r19,r25 ; v1 += edge 1 x ec: a41b a001 add r45,r1,8 ; frag + 1 f0: 910f 4987 fadd r20,r20,r26 ; v2 += edge 2 x f4: 047c 4000 strd r16,[r1] ; *frag = ( x, 1/w ) f8: 69ff 000a orr r3,r2,r3 ; v0 < 0 || v1 < 0 || v2 < 0 || (z buffer test) fc: 278f 4907 fadd r17,r17,r23 ; 1/w += 1/w x 100: 347f 1402 movgte r1,r45 ; frag = !test ? frag + 1 : frag 104: 947f a802 movgte r44,r21 ; oldzw = !test ? newzw : oldzw 108: 90dc a500 str r44,[r12,-0x1] ; zbuffer[-1] = zvalue 10c: b58f 4987 fadd r21,r21,r27 ; newz += z/w x increment 110: 90cc a600 ldr r44,[r12],+0x1 ; oldzw = *zbuffer++; 114: 009b 4800 add r16,r16,1 ; x += 1
Nothing wasted eh?
Using rounding mode there are I think 4 stalls (i'm not, but i should be). One when orring in the result of the zbuffer test and three between the last fadd and the first fsub. Given the whole lot is 10 cycles without the stalls that doesn't really leave enough room to do any better for the serial-forced sequence of 2 flops + load + store required to implement the zbuffer. To do better I would have to unroll the loop once and use ldrd/strd for the zbuffer which would let me do two pixels in 30 instructions rather than one in 16 instructions. It seems insignificant but if the scheduling improved such that the execution time went down to the ideal of 10 cycles and then an additional cycle was lopped off - from 14 to 9 cycles per pixel - that's a definitely not-insignificant 55% faster for this individual loop.
The requirement of even-pixel starting location is an added cost though. Ahh shit i dunno, externalising the edge tests might be more fruitful, but maybe not.
Although there are some other things I haven't gotten to yet i've pretty much convinced myself this design is a dead-end now mostly due to the overhead of fragment transfer and poor system utilisation.
First I will put the rasterisers and fragment shaders back together again: splitting them didn't save nearly as much memory as I'd hoped and made it too difficult to fully utilise the flops due to the work imbalance and the transfer overheads. I'm not sure yet on the controller. I could keep the single controller and gang-schedule groups of 2/3/4 cores from the primitive input - i think some sort of multiplier is necessary here for bandwidth. Or I could use 3 or 4 of the first column of cores for this purpose since they all have fair access to the external ram.
I've looked at some of this before but it's been a while and never had much use for it.
I started with "wavelet noise" but when I realised it needed big lookup tables I went back to looking at the simplex noise algorithm. It seems wavelets are being used to create bandwidth limited versions of existing noise so that it scales better; but this isn't something I need to worry about.
A paper and implementation by Stefan Gustavson and others pretty much had me covered but I wanted to try and remove the 512+256 element lookup tables used to hash the integer coordinates to save some memory on the epiphany.
I came up with two working solutions in the end.
The first one uses a 32-element lookup table of prime numbers to implement a 2D hash function. I just grabbed the first 32 primes (20 apart) for the table and fiddled with eor/mul and shift until I had something that seemed to work. I arbitrarily chose 32 because it was a nice round number.
// there's nothing particularly good or useful here
static final int[] hasha = {
71, 173, 281, 409, 541, 659, 809, 941,
1069, 1223, 1373, 1511, 1657, 1811, 1987, 2129,
2287, 2423, 2617, 2741, 2903, 3079, 3257, 3413,
3571, 3772, 3907, 4057, 4231, 4409, 4583, 4751
};
private static int hash16(int a, int b) {
return ((((b ^ hasha[a & 31]) * (a ^ hasha[b & 31])) >> 5) & 15);
}
Because I was only interested in the 2D case I changed the gradient normal array to 16 elements so I didn't have to modulo the result as well. TBH it's kind of surprising it works as well as it does since hashing numbers is pretty tricky to get right and I really didn't know what I was doing.
When I started I didn't realise exactly what it was for so once I had a better understanding of why it was there I thought i'd try an existing integer hash function. In general they failed miserably but I found one that came from the h2 database which worked sufficiently well.
private static int hash(int x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x);
return x;
}
private static int hash16(int a, int b) {
return (hash(a * b + a + b)) & 15;
}
I used the (a*b+a+b) calculation to turn it into a 2D hash function.
So this final version requires no lookup table for the gradient table permute at all - nice. But it requires 3 integer multiplies - not so nice for epiphany. And even the other version needs an integer multiply and thus the same costly fpu mode changes on epiphany.
Since I only need a limited number of output bits it might (should?) be possible to change this to using float multiplies to avoid the costly mode change; but this is something for further study. The first version might make this easier.
Screenshots ... this first is a simple 4-octave fractal noise generated using the 2D Simplex Noise code from Stefan. I think the 2D noise function has a small bug because it's using the 12-point 3D gradient bases which don't always evaluate to vectors of the same length in 2D but it isn't apparent once fractal noise is generated as here.
The next one is an example using the naive hash function (it may be a different scale to the others since I ran it separately). Covering 4 octaves hides some problems it might have but I've done some very basic testing to larger scales and it seems about as stable and nicely random as the others.
And the final shot is using the M2 hash function and 16 gradients evenly spaced around the unit circle rather than 12 evenly spaced around the unit sphere as in the traditional version.
Look about the same to me?
I don't know if it's useful for anything I might do or if it is even fast enough to run in a shader on the epiphany but I learnt a couple of interesting things along the way.
I've been doing some little bits and pieces on the ezegpu code as well.
Together the NEON changes amount to a 6% improvement to the total runtime of the all-ARM code for my current testing case (8x8x8 stars). Nothing major, although it goes up on simpler scenes mostly due to the faster RGBA float to byte conversion.
It is being executed over a good number of steps over range of scales and tested at every pixel location of the given scale.
To be usable as a robust face detector further post-processing on the raw hit rectangles must be performed and then further work is needed to weed out false positives such as the NASA logo or hands which would still pass this process. Together with a wise choice of search scale.
The following is the raw output from a short training run of the fodolc algorithm over the same scale range. This is a 20x20 face detector which requires exactly 400 tests of a 4 bit local binary pattern (LBP) encoded image and 800 bytes of data storage at runtime. This is using a loose threshold to give comparable results to the haar cascade and to see what sort of features give false positives.
Unlike the haar cascade the output is simply a distance. This can simplify the post-processing to a threshold and basic non-minimal suppression trough detection.
As an example the following the raw output from the same fodolc detector but with a tighter threshold.
There are still some false positives but obviously it is something of an improvement - trivial trough detection would clean it up to a point exceeding the result of the haar cascade.
This is only a weak classifier taken from just the first 15 minutes or so of classifier training on 10 000 training images extracted or synthesised solely from 880 portrait photographs. Longer training always generates a better detector. A higher quality training set should generate a better detector. Training is by a very basic genetic algorithm.
In Java on a beefy workstation the execution time is roughly the same between the two algorithms but the fodolc algorithm can be implemented in efficient SIMD or OpenCL/GPU with very little effort for significant (order of magnitude) gains.
The following is the entire code of the classifier outside of the LBP conversion and of course the classifier table itself.
// Can you copyright something so simple??
public class Classify {
private final static short[] face = { ... };
public int score(byte[] lbp, int stride, int xi, int yi) {
int score = 0;
for (int y=0,i=0;y<20;y++)
for (int x=0;x<20;x++,i++)
score += (face[i] >>> lbp[x+xi+(y+yi)*stride]) & 1;
return score;
}
}
Fast Face Detection in One Line of Code has a link to an unpublished paper with brief overview of the algorithm and local binary pattern used.
Please comment on this post if you think this is interesting. Or even if you're just as dumbfounded as I am that something so simple could possibly work.
The face detector was trained using images from the FERET database of facial images collected under the FERET program, sponsored by the DOD Counterdrug Technology Development Program Office (USA).
http://a-hackers-craic.blogspot.com.au/2014/08/a-weak-face-detector.html
So far for graphical output i've just been using Swing: actually there's probably not much reason not to use it for that because it does the job but once you need to add some interactivity it becomes a bit of a pain if you've been playing with JavaFX. I might add a 'display intermediate image' anywhere in the code and up it comes.
But JavaFX doesn't let you just call Platform.runLater() or new Stage() from anywhere as with Swing: the system needs initialising within an Application context.
Here's a solution. I have no claims it's a good one but it works for me so far.
// This code is placed in the public domain
public class FXUtils {
static FXApplication app;
static Semaphore sem = new Semaphore(0);
public static void startFX(Runnable r) {
if (app == null) {
try {
Thread t = new Thread(() -> {
FXApplication.start(r);
});
t.start();
sem.acquire();
} catch (InterruptedException ex) {
}
} else {
Platform.runLater(r);
}
}
public static class FXApplication extends Application {
WritableImage image;
static Runnable run;
public FXApplication() {
}
@Override
public void start(Stage stage) throws Exception {
app = this;
run.run();
sem.release();
}
public static void start(Runnable r) {
run = r;
// Application.launch() can only be called from a static
// method from a class that extends Application
Application.launch();
// no windows - no app!
System.exit(0);
}
}
}
Whether start() calls System.exit() or not is up to you - personally when I close a window i'm prototyping stuff on I want everything else to fuck off for good.
And this is how to use it:
public static void main(String[] args) {
FXApplication.start(() -> {
// Now on javafx thread
Stage s = new Stage();
s.setScene(new Scene(new VBox(new Label("foobar!"))));
s.show();
});
// Will wait for javafx to start, but then continue here
// exiting will leave the windows open, till they're closed
}
This uses a thread to launch javafx so that the original main thread can continue; Application.launch() doesn't return until the last window is closed so would otherwise block. The thread could be made a daemon too for some different behaviours.
If you just want to launch a full JavaFX application from multiple mains then none of this is required, just create a static start() method which calls Application.launch().
One thing I was curious about was whether I could use streams to simplify the prototyping by saving having to type and retype the typical processing loop:
for (int y = 0; y < image.height; y++) {
for (int x = 0; x < image.width; x++) {
do something;
}
}
When i'm prototyping stuff I type this in ... a lot.
I had mixed results.
Because I wanted to support arbitrary 2d subregions of an image which might be a mapping of an arbitrary 2d subregion I had to create my own 'spliterator' to do the work. After a couple of aborted attempts I came up with one that just turns the widthxheight range into a linear stream and then maps that to the local (x,y) when retrieving the pixel values (i tried to avoid the divide first, but made a pigs breakfast of the maths).
It lets me write something like this to calculate the histogram over a sub-range of an image:
Image2D img;
byte[] hist = new byte[256];
img.bytes(0, 0, 16, 16).forEach((v) -> > {
hist[v] += 1;
});
Ok, so far so good. It's not necessarily the best way to do it - it can't be parallelised for instance, but this is fine, it saves a few keystrokes and it lets one access a whole bunch of stream functionality "for free".
The problem is with images you normally want to write to them or modify them. So you're back to just using a loop, or maybe a custom foreach which supplies coordinates to a lambda function: again this is fine but then you don't get any of the stream functionality for free here (although as in the next section: it's good enough?). You could just use an IntStream, ... but that doesn't really save any typing over a for loop.
Staying within the confines of the existing IntStream type for the sake of argument, the solution is a little clumsy. One first has to create a class which implements the functions required to be used as a collector.
static class ByteArray {
byte[] data;
public void add(int b);
public void addAll(ByteArray b);
}
With that in place it can be used to collect the results of the calculation. In this case performing the pixel mapping from one set of intensity values to another.
byte[] pixels = img.bytes()
.map((int v) -> map[operand])
.collect(ByteArray::new, ByteArray::add, ByteArray::addAll)
.data;
Image2D dst = new ByteImage(src.width, src.height, pixels);
This can run in parallel: the downside is that each stage needs to allocate its own buffers and then allocate copies of these up to the final result. Probably works but yeah, it's not that pretty or efficient.
So I thought about it a little and perhaps a solution is to create another type of stream which indexes over the values. Some of the api usage gets a bit fatter if you want to use some of the basic stream facilities like sums and so on: but that's what .map() is for. I think it can get away without having to allocate the indexing object for each iteration: it is only needed when the stream range is split.
class IndexedInt {
int value;
int x;
int y;
}
dst = new ByteImage(src.width, src.height);
img.bytes().forEach((ii) -> {
dst.set(ii.x, ii.y, ii.value);
});
I dunno, I suppose that's better than a double-for-loop, once the not-insignificant scaffolding is in place.
Actually; why bother even passing the value in this case, it may as well just be calculating indices. It doesn't really make any difference to the code and having a general purpose 2D indexer is somewhat useful.
class Index2D {
int x;
int y;
}
dst = new ByteImage(src.width, src.height);
Index2D.range(0, 0, src.width, src.height)
.forEach((ii) -> {
dst.set(ii.x, ii.y, src.get(ii.x, ii.y));
});
Some of the functionality is a little less concise but the simplicity of the above is probably worth it.
double average = Index2D.range(0, 0, src.width, src.height)
.mapToInt((ii) -> img.get(ii.x, ii.y))
.average()
.getAsDouble();
Much of that could be hidden in helper functions and the external interface could remain an IntStream, for cases where the pixel locations are not required.
Seems like a lot of work just to get a free parallelisable 'sum' function though? The implementing classes still need a bunch of boilerplate/helpers and they could have just implemented most of that themselves. I don't find the forkJoin() approach to paralellisation (which is used by the streams code) to be very efficient either.
But this is my first real look at it : experiments ongoing.
I mentioned earlier that the histogram calculation using a forEach isn't paralleisable as is (one could add a synchronized block inside the loop but one would have to be both naive and stupid to do so).
It can be parallelised using a collector. TBH it's a lot of boilerplate for such a simple function but the algorithm is identical to the one you would use in OpenCL even if it doesn't look the same.
First, one needs the class to hold the results and intermediate results.
class Histogram {
int[] hist;
public Histogram() {
hist = new int[256];
}
public void add(int value) {
hist[value] += 1;
}
public void addHistogram(Histogram o) {
for (int i = 0; i < hist.length; i++)
hist[i] += o.hist[i];
}
}
And then the code:
int[] hist;
Image2D img;
hist = img.bytes().parallel()
.collect(Histogram::new, Histogram::add, Histogram::addHistogram)
.hist;
*shrug*. I guess it saves some typing?
The basic technique is straightforward: double-word loads must be used to load every floating point value otherwise there are too may ialu ops, and once that is established one just needs enough of a calculation to fit in a loop to remove all dependency stalls by unrolling it some number of times.
The details are important though, my first cut didn't delay the fmadd's enough - but ezetime showed this very obviously so it was easy enough to fix.
Actually it's not that straightforward: the inner loop itself also needs to be pipelined - so not only is it unrolled 8 times the 8 steps have been split into two stages temporally separated by half a loop each so it's "effectively" been unrolled 16x. Infact it's a bit better than that because no amount of loop unrolling could hide the data loads completely if each loop were independent. In this case it just needs to perform 0.75 loops incoming (all the loads and half the flops) and 0.25 loops outgoing (the remaining half the flops) outside of the loop to prepare/complete the calculation so the loop count is set to one less than required.
So here's a dump from running ezetime over the assembled code. Of interest is the inner loop where every instruction pair dual-issues and a new fmadd is issued every cycle.
0123456789012345678901234567890123456789012345678901234567890123
_fmadd:
00000000: movts.l special.0.5,r2 | ---1 |3
00000004: mov.l r2,#0x0000 | ---1 |3
00000008: movts.s special.0.6,r2 | ---1 |3
0000000a: mov.l r2,#0x0000 | ---1 |3
0000000e: movts.s special.0.7,r2 | ---1 |3
00000010: mov.l r16,#0x0000 | ---1 |3
00000014: mov.l r17,#0x0000 | 1 |
00000018: mov.l r18,#0x0000 | 1 |
0000001c: mov.l r19,#0x0000 | 1 |
00000020: mov.l r20,#0x0000 | 1 |
00000024: mov.l r21,#0x0000 | 1 |
00000028: mov.l r22,#0x0000 | 1 |
0000002c: mov.l r23,#0x0000 | 1 |
00000030: ldrd.l r48,[r0],#+1 | 12 |
00000034: ldrd.l r56,[r1],#+1 | 12 |
00000038: ldrd.l r50,[r0],#+1 | 12 |
0000003c: ldrd.l r58,[r1],#+1 | 12 |
00000040: ldrd.l r52,[r0],#+1 /| 12 |
00000044: fmadd.l r16,r48,r56 \| 1234 |
00000048: ldrd.l r60,[r1],#+1 /| 12 |
0000004c: fmadd.l r17,r49,r57 \| 1234 |
00000050: ldrd.l r54,[r0],#+1 /| 12 |
00000054: fmadd.l r18,r50,r58 \| 1234 |
00000058: ldrd.l r62,[r1],#+1 /| 12 |
0000005c: fmadd.l r19,r51,r59 \| 1234 |
hw_loop_s:
00000060: ldrd.l r48,[r0],#+1 /| 12 |
00000064: fmadd.l r20,r52,r60 \| 1234 |
00000068: ldrd.l r56,[r1],#+1 /| 12 |
0000006c: fmadd.l r21,r53,r61 \| 1234 |
00000070: ldrd.l r50,[r0],#+1 /| 12 |
00000074: fmadd.l r22,r54,r62 \| 1234 |
00000078: ldrd.l r58,[r1],#+1 /| 12 |
0000007c: fmadd.l r23,r55,r63 \| 1234 |
00000080: ldrd.l r52,[r0],#+1 /| 12 |
00000084: fmadd.l r16,r48,r56 \| 1234 |
00000088: ldrd.l r60,[r1],#+1 /| 12 |
0000008c: fmadd.l r17,r49,r57 \| 1234 |
00000090: ldrd.l r54,[r0],#+1 /| 12 |
00000094: fmadd.l r18,r50,r58 \| 1234 |
00000098: ldrd.l r62,[r1],#+1 /| 12 |
0000009c: fmadd.l r19,r51,r59 \| 1234 |
hw_loop_e:
000000a0: fmadd.l r20,r52,r60 | 1234 |
000000a4: fmadd.l r21,r53,r61 | 1234 |
000000a8: fmadd.l r22,r54,r62 | 1234 |
000000ac: fmadd.l r23,r55,r63 | 1234 |
000000b0: fadd.l r16,r16,r17 | 1234 |
000000b4: fadd.l r18,r18,r19 | 1234 |
000000b8: fadd.l r20,r20,r21 | 1234 |
000000bc: fadd.l r22,r22,r23 | -1234 |1
000000c0: fadd.l r16,r16,r18 | -1234 |1
000000c4: fadd.l r20,r20,r22 | --1234 |2
000000c8: fadd.l r0,r16,r20 | ----1234 |4
000000cc: jr.l r14 | 1 |
Over 2048 data elements it executes in 2089 cycles plus a couple dozen for the function invocation and hardware timer setup overheads. I used 2x8k buffers one in bank 1 and the other in bank 2.
Once it finishes the inner loop it completes the calculations for the data pre-loaded during the final iteration and then sums across the 8 partial sums in 3 parallel steps.
A compatible/equivalent C function taking the same args would be:
// len8s1 == element count / 8 - 1
float fmadd(const float *a, const float *b, int len8s1) {
int count = (len8s1+1)*8; // 'unroll' the count
float c = 0;
for (int i=0; i < count; i++)
c += a[i] + b[i]; (oops)
c += a[i] * b[i];
return c;
}
I haven't validated that it produces the correct calculation but apart from a typo or something it should be correct.
The movts instructions near the start of the listing above are lc, ls, and le respectively (loop count, loop start, loop count) for the hardware loop feature; ezetime doesn't output the register aliases. This is also for an unlinked object so the addresses are all zero - but it sets ls to (hw_loop_e-4) for those who might understand what that means, i just put the label where it is to make the loop more readable. I fiddled with the size of the movts instructions till i got the alignment right so it doesn't need any nops for that alignment. Also, the movts instruction cycle timing isn't meant to be correct.
PS Another 8 cycles could be knocked off if the first loop just used fmul since the 8xloads of 0.0 could be removed; but then it would need 1.75 loops before starting the inner loop
It was supposed to be a super-quick chuck-together of what I had but I cleaned up the code and did a big re-factor (everything was in one namespace) and a bunch more. Toolification, building, packaging, readme, webpage, ... so this post will be short.
I haven't done much testing/verification beyond a few small test-cases, so bugs are a given.
It's on the ezetool (now with ezetime(tm)) home page, as is an example of the current outputs.
