Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

Benchmark Contest:Count character ratio in DNA file

Name: Anonymous 2015-04-12 12:19

RULES:
The program must count(without prior knowledge of file beyond its format) GC-content of source file.
GC-content is fraction of GC vs AT chars found in the file expressed as floating point number. http://en.wikipedia.org/wiki/GC-content
source file https://github.com/dubst3pp4/GC-Content-OOC/blob/master/Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa

Name: Anonymous 2015-04-12 12:40

Why limit to only 4 characters? Why not formulate this problem as a more general problem of the frequency of characters from some arbitrary subset in a stream of arbitrary characters? Do you idiots think you're smarter just for using the word "DNA", or do you think that making solutions ungeneral somehow adds to their "practicality"?

Name: Anonymous 2015-04-12 13:13

>>2
do you think that making solutions ungeneral somehow adds to their "practicality"?
small minded people really do think this, it helps motivate them because they are not capable of understanding that a general thing has many intstances.

Name: Cudder !cXCudderUE 2015-04-12 15:32

http://saml.rilspace.org/moar-languagez-gc-content-in-python-d-fpc-c-and-c

tl;dr: C wins. ...but no Asm in the comparison. And talking about reading a file "lines" at a time? WTF, are these amateurs? Even the C version there is rather slow - around 2 clocks/byte.

But if you take this...

C = 63h = 0110 0011b
G = 67h = 0110 0111b
A = 61h = 0110 0001b
T = 74h = 0111 0100b

...and SSE it, you can get 16 bytes/clock. So even the best C solution there is ~32x slower than what the CPU can do.

Name: Anonymous 2015-04-12 15:45

>>4
No one forces you to read the file by line, its not in >>1 Rules.

Name: Cudder !cXCudderUE 2015-04-12 16:37

>>5
I was talking about the implementations in http://saml.rilspace.org/calculating-gc-content-in-python-and-d-how-to-get-10x-speedup-in-d and the other link from there. Apparently his excuse is "Many people suggested to read the whole file in once instead of reading line by line though. This can cause problems with the many very large files in bioinformatics" but this ignores the fact that the lines don't matter a rat's arse in this situation as all you're doing is a series of filtered counts. It's like writing a wc or cat that reads a line at a time - a retardedly stupid way of doing it that only a n00b would come up with.

Name: Anonymous 2015-04-12 20:00

The best result with no lookup tables/simd/threads(108mcycles)
#include "void.h" //gist.github.com/FrozenVoid/87e6ad6212ac9ce496e0#file-void-h"
STDSTART
#define dmask(c) dmasku8(((u8)c))
#define dmasku8(c) (c+(c<<8)+(c<<16)+(c<<24)+(c<<32)+(c<<40)+(c<<48)+(c<<56))
#define modz255(x) sm u8 c=(x);u8 dv=(c/255);c-((dv<<8)-dv) em
const u8 inverse0div= ((~(0ULL))/255ULL);
#define inv0mul(x) (inverse0div*(127+(x)))
#define xmaskinv(x) ((x)&(inverse0div*127))
#define countless(x,n) \
(((( inv0mul(n)-xmaskinv(x) )&(~(x))&(inverse0div<<7))/128)%255ULL)
#define dcless(x,n) ((( inv0mul(n)-xmaskinv(x) )&(~(x))&(inverse0div<<7))>>7)
//count 0s
#define dnacount(xh,ms1,ms2) ((dcless((xh^ms1),1)+dcless((xh^ms2),1))) %255
#define dnacount2(xh,ms1,ms2) sm u8 mk1=xh^ms1;u8 mk2=xh^ms2;\
u8 inv0m=inv0mul(1);\
(((( inv0m-xmaskinv(mk1) )&(~(mk1))&(inverse0div<<7))>>7)+((( inv0m-xmaskinv(mk2) )&(~(mk2))&(inverse0div<<7))>>7) )%255 \
em
#define dnacount3(xh,ms1,ms2) sm u8 inv0d=inverse0div<<7;\
u8 inv0m=inv0mul(1);\
modz255(((( inv0m-xmaskinv(xh^ms1) )&(inv0d))>>7)+((( inv0m-xmaskinv(xh^ms2) )&(inv0d))>>7) ) \
em
#define dnacountfunc dnacount3
u8 i=0,j;u8 countGC=0,countTA=0;f8 res;;u1 p;
if(argc<2)quit("No args");u8 fsize=filesize(argv[1]);
if(!fsize)quit("Invalid file");u1p in=filecontent(argv[1]);
//file load speed is dependent on hardware(SSD brands/HDD location in the disk)
u8 st=tsc();for(in[i]=='>';in[i]!='\n';i++);;
while((u8)(&in[i])%8){
countGC+=((in[i]=='G')|(in[i]=='C'));
countTA+=((in[i]=='T')|(in[i]=='A'));i++;}
//8byte chunks MAINLOOP (1thread)
u8 n=i/8,nmax=(fsize/8); u8p inp=(u8p)in;
for( n=i/8;n<nmax;n++){
countGC+=dnacountfunc(inp[n],dmask('G'),dmask('C'));
countTA+=dnacountfunc(inp[n],dmask('T'),dmask('A'));}
for(u8 i=n*8;i<fsize;i++){p=in[i];
countGC+=!((p!='G')&(p!='C'));
countTA+=!((p!='T')&(p!='A')); }
res=((f8)countGC)/(((f8)countGC)+((f8)countTA));
u8 et=tsc();
p("Found GC/GCTA ratio:",res," of file",argv[1],
" in ",et-st,"cycles\n GC:",countGC," TA:",countTA);
/* Found GC/GCTA ratio: 0.376217301393862 of file Homo_sapiens.GRCh37.67.dna_rm.
chromosome.Y.fa in 108865000 cycles
GC: 3228502 TA: 5352980 */ STDEND

Name: Cudder !cXCudderUE 2015-04-13 5:19

>>7
12.7 cycles/byte is not impressive at all.

Name: Anonymous 2015-04-13 5:25

46mcycles, 2 threads + minor fixes.
#include "void.h" //gist.github.com/FrozenVoid/87e6ad6212ac9ce496e0#file-void-h"
STDSTART
#define dmask(c) dmasku4(((u4)c))
#define dmasku4(c) (c+(c<<8)+(c<<16)+(c<<24))
#define modz255(x) sm u4 c=(x);u4 dv=(c/255);c-((dv<<8)-dv) em
#define modx255(x) sm u4 c=(x);u4 dv=c/3/5/17;c-((dv<<8)-dv) em

#define inverse0div ((~(0UL))/255UL)
#define inv0mul(x) (inverse0div*(127+(x)))
#define xmaskinv(x) ((x)&(inverse0div*127))

#define inv0d (inverse0div<<7)
#define inv0d127 (inv0d-inverse0div)
#define inv0m (inv0mul(1))
#define countless(x,n) \
(((( inv0mul(n)-xmaskinv(x) )&(~(x))&(inverse0div<<7))/128)%255UL)
#define dcless(x,n) ((( inv0mul(n)-xmaskinv(x) )&(~(x))&(inverse0div<<7))>>7)
//count 0s
#define dnacount(xh,ms1,ms2) ((dcless((xh^ms1),1)+dcless((xh^ms2),1))) %255
#define dnacount2(xh,ms1,ms2) sm u4 mk1=xh^ms1;u4 mk2=xh^ms2;\
(((( inv0m-xmaskinv(mk1) )&(~(mk1))&(inverse0div<<7))>>7)+((( inv0m-xmaskinv(mk2) )&(~(mk2))&(inverse0div<<7))>>7) )%255 \
em
#define dnacount3(xh,ms1,ms2) sm modz255(((( inv0m-xmaskinv(xh^ms1) )&(inv0d))>>7)+((( inv0m-xmaskinv(xh^ms2) )&(inv0d))>>7) ) \
em

inline u4 dnacount3f(u4 xh,u4 ms1,u4 ms2){

re modz255(((( inv0m-xmaskinv(xh^ms1) )&(inv0d))>>7)+((( inv0m-xmaskinv(xh^ms2) )&(inv0d))>>7) ) ;;}

#define xmaskinv4(x) sm u4 y=x; ((y)&(inv0d127)) em

#define dnacount4( xh, ms1, ms2) modx255((( (( inv0m-xmaskinv4(xh^ms1) )&(inv0d)))+((( inv0m-xmaskinv4(xh^ms2) )&(inv0d))) )>>7)

#define dnacountfunc dnacount4
u8 i=0,j;u8 countGC=0,countTA=0;f8 res;;u1 p;
if(argc<2)quit("No args");u8 fsize=filesize(argv[1]);
if(!fsize)quit("Invalid file");u1p in=filecontent(argv[1]);
//file load speed is dependent on hardware(SSD brands/HDD location in the disk)
u8 st=tsc();for(in[i]=='>';in[i]!='\n';i++);;
while((u8)(&in[i])%4){
countGC+=((in[i]=='G')|(in[i]=='C'));
countTA+=((in[i]=='T')|(in[i]=='A'));i++;}
//4byte chunks MAINLOOP 2thread
u4p inp=(u4p)in;

u8 n=i/(sizeof(inp[0])), nmax=(fsize/(sizeof(inp[0])));

//assuming 2 cores
#pragma omp parallel sections
{

#pragma omp section
for( n=i/(sizeof(inp[0]));n<nmax;n++){
countGC+=dnacountfunc(inp[n],dmask('G'),dmask('C'));}
#pragma omp section
for( n=i/(sizeof(inp[0]));n<nmax;n++){
countTA+=dnacountfunc(inp[n],dmask('T'),dmask('A'));}
}
for(u8 i=n*(sizeof(inp[0]));i<fsize;i++){p=in[i];
countGC+=!((p!='G')&(p!='C'));
countTA+=!((p!='T')&(p!='A')); }
res=((f8)countGC)/(((f8)countGC)+((f8)countTA));
u8 et=tsc();
p("Found GC/GCTA ratio:",res," of file",argv[1],
" in ",et-st,"cycles\n GC:",countGC," TA:",countTA);
/* Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa
Found GC/GCTA ratio: 0.376217301393862 of file Homo_sapiens.G
hromosome.Y.fa in 49437998 cycles
GC: 3228502 TA: 5352980*/ STDEND

Name: Anonymous 2015-04-13 5:30

>>8 Learn some math
60,363,186 bytes in file
1 thread 108,000,000 cycles =1.8 cycles per byte
2 threads 46,000,000 cycles =0.76 cycles per byte
And thats with PentiumG3220

Name: Cudder !cXCudderUE 2015-04-13 5:34

>>10
NO U

GC: 3228502 TA: 5352980
3228502 + 5352980 = 8581482 bytes
108865000 / 8581482 = ~12.686

Name: Anonymous 2015-04-13 5:38

>>11 You are counting occurrences of letters, not bytes.
I could prefilter the file to contain only GCTA and still get >>10

Name: Anonymous 2015-04-13 5:50

>>11
..You actually didn't view the file at all and assume things from code.

Name: Anonymous 2015-04-13 6:32

"fastest" version from
http://saml.rilspace.org/moar-languagez-gc-content-in-python-d-fpc-c-and-c is
https://gist.github.com/samuell/5559717
37.6217301394 in 922,484,508 cycles(20 times slower than 46 million)
according to Cudder its >>4 "2 clocks/byte" mine is 20 times faster so 0.1 clocks/byte or 10 bytes per clock(and no SSE intrinsics used).
(in reality its 0.76 clocks/byte)
Here is the source of the "2 clocks per byte"(with added rdtsc)
#define __USE_MINGW_ANSI_STDIO 1
#include <stdio.h>

int main()
{
char buf[1000];
int gc=0;
int total=0;
char tablegc[256]={0,};
char tabletotal[256]={0,};
FILE *f=fopen("Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa","r");
unsigned long long st=__rdtsc();
tabletotal['A']=1;
tabletotal['T']=1;
tabletotal['C']=1;
tabletotal['G']=1;
tablegc['C']=1;
tablegc['G']=1;
while (fgets(buf,1000,f))
if (*buf!='>') {
char c, *ptr=buf;
while ((c=*ptr++)) {
total+=tabletotal[(int)c];
gc+=tablegc[(int)c];
}
}

unsigned long long et=__rdtsc();
fclose(f);
printf("%.10f in %llu cycles\n",(100.*gc)/total,et-st);
return 0;
}

Name: Anonymous 2015-04-13 6:36

>>14 Nevermind he meant the Whole file version probably which is much faster.

Name: Anonymous 2015-04-13 6:40

Cudder is all talk and one fizzbuzz

Name: Anonymous 2015-04-13 9:02

>>15 28Mcycles with precomputed tables. Its less flexible though.
>>16 http://bbs.progrider.org/prog/read/1423332691/4 -> http://codepad.org/VONAd6J5 it segfaults(i think he attempted to cleverly use the stack to print a string with a function pointer)

Name: Anonymous 2015-04-13 9:41

>>17 Oh, and thats some kind of stack exploit probably since it depends on printing function address(will not work with ASLR)

Name: Cudder !cXCudderUE 2015-04-13 14:17

>>13
I'm not going to download a random 58MB file just for the fun of it, nor an 8MB one.

>>17,18
This retard couldn't even figure out the platform. What a n00b.

Name: Anonymous 2015-04-13 15:24

>>19 Have you considered upgrading from dialup?

Name: Anonymous 2015-04-14 1:37

anus meets penis

Name: Anonymous 2015-04-14 1:54

Benchmark contest: count doubles ratio in a thread.

Name: Anonymous 2015-04-15 0:15

>>19
it takes a special kind of moron to write a platform-specific fizzbuzz in C

Name: Anonymous 2015-04-15 0:17

>>23
stop talking to it. you just fuel it

Name: Anonymous 2015-04-15 1:03

anus engulfs penis

Name: Anonymous 2015-04-15 1:05

anus massages penis

Name: Anonymous 2015-04-15 1:10

penis begins moving in and out of the tight anus

Name: Anonymous 2015-04-15 1:12

penis shudders in ecstasy from the warm sticky blood-scented anus

Name: Anonymous 2015-04-15 1:14

penis pulls out and ejaculates a stream of black across the room.
The stream takes the shape of a large black snake.
``HAVE YOU READ YOUR SICP TODAY?''

Name: Anonymous 2015-04-15 4:49

anus haxxes penis

Name: Anonymous 2015-04-15 6:20

prime get
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -