LinuxQuestions.org - Count the line

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - Count the line (https://www.linuxquestions.org/questions/programming-9/count-the-line-858487/)

My question is about the same as the one posed here, but I'm not satisfied about the conclusion to use 'wc -l'
http://www.linuxquestions.org/questi...-files-583991/

I have a zabbix monitoring server and I am executing the following line each minute on each client

Code:

wc -l /proc/net/ip_conntrack

This is a piece of cake on most servers, but on 1 server it will take about 13 seconds as it has more about 40.000 (ligit) connections open.

I just want to count the lines to get the amount of connections. "wc -l" does more than I want it to and I'm hoping a program that just counts the lines and only does that, can do this in a faster way.

I am not good with C. I used it 20 years ago to manipulate strings when things became too slow in the native language (Clipper). I did write some nice things in C at the time, so it wonders me somehow why I can't do it (maybe I should try harder).

I tried to alter this program which does a bit more than just count the line, but didn't succeed (how embarassing).

http://www.gnu.org/software/cflow/ma...c-command.html

Could someone take a look at it?
I was thinking of calling it 'lc' and it should only return the amount of '\n'
Hopefully the binary is faster than 13 seconds...

Well I am not sure of the speed comparison, but how does something like this compare:

Code:

grep -c . /proc/net/ip_conntrack

The upside is blank lines will be skipped, the downside is a line with only white space will be counted. There are ways to counter this but of course they may slow it down.

I did manage to alter that C-program and was able to compile an 'lc', but was disappointed to see it perform this bad. I also benchmarked the 'grep' and it performed the same as wc -l.
Here's my patched 'wc' http://pastebin.com/KUM0EwnN
I compiled it with 'gcc lc.c -o lc'

Code:

# time ./lc /proc/net/ip_conntrack

 38504 /proc/net/ip_conntrack



real    0m41.469s

user    0m0.152s

sys    0m38.682s

# time wc -l /proc/net/ip_conntrack

38059 /proc/net/ip_conntrack



real    0m10.162s

user    0m0.008s

sys    0m9.889s

# time grep -c . /proc/net/ip_conntrack

38192



real    0m10.115s

user    0m0.016s

sys    0m9.925s

wc has been developed over years by clever people.
all the bugs have been killed years ago.

I doubt very much it can be improved upon.
you are wasting your time if you think you can
improve upon basic unix tools.

I suggest your 13 seconds bottleneck is unlikely to be in wc

Quote:

Originally Posted by bigearsbilly (Post 4236900)

all the bugs have been killed years ago.

Severly doubt that, no program is completely free of bugs, since, imho, a bug can also be between the screen and the chair ;)

Quote:

Originally Posted by bigearsbilly (Post 4236900)

I doubt very much it can be improved upon.
you are wasting your time if you think you can
improve upon basic unix tools.

If everyone thought like that then we would still be using Assembly or maybe even PunchTape.

;)

Code:

# time ./lc /proc/net/ip_conntrack

 38504 /proc/net/ip_conntrack



real    0m41.469s

user    0m0.152s

sys    0m38.682s

# time wc -l /proc/net/ip_conntrack

38059 /proc/net/ip_conntrack



real    0m10.162s

user    0m0.008s

sys    0m9.889s

Most of the time is in sys, which suggests that increasing the buffer size to reduce the number of calls to read(2) may help.

Quote:

Originally Posted by bigearsbilly (Post 4236900)

wc has been developed over years by clever people.
all the bugs have been killed years ago

I'm not suggesting at all that 'wc' has bugs or written inefficient.
wc can do much more than just count lines and I assume it has some code in it that is able to count words instead of lines and it may execute a bit of code to test something that never changes.

I already found this page: http://www.stokebloke.com/wordpress/...they-are-slow/
which suggests the library function 'getc' should not be used, but fread is OK.

For someone using C on a daily basis it should be a piece of cake to rewrite 'lc'

BTW, the "wc" which I patched to make "lc" is not the one which is widely used. Maybe I should get hold of that one and try to modify that (take code out) to speed it up.

I think the key is into taking a big chunk of data each time you call the library function (getc,fread) and put that in a piece of static memory and count the amount of '\n'.

About improving code....
I can remember (20 years ago) speeding up a soundex() function for Clipper. They gave an example in assembly. I used my own algorithm for it and did it in C. Mine was 1000 times faster.

may I suggest ...

Code:

cat -n /proc/net/ip_conntrack | tail -1 | awk '{print $1}'

"cat" is super fast and awk will receive just one line to output only the number....anyway, is just a crazy idea to test.

Quote:

Originally Posted by frater (Post 4237167)

I just download coreutils and took a look at the source of 'wc'.
They already have a seperate loop for just counting lines, so I don't think it can be optimized that easily.

Maybe someone can still see some posibilities?
Can't it use a static piece of memory (buffer) which is then parsed and counted?
memchr is a library function, should a library function be used per se?

Code:

      /* Use a separate loop when counting only lines or lines and bytes --

        but not chars or words.  */

      while ((bytes_read = safe_read (fd, buf, BUFFER_SIZE)) > 0)

        {

          char *p = buf;



          if (bytes_read == SAFE_READ_ERROR)

            {

              error (0, errno, "%s", file);

              ok = false;

              break;

            }



          while ((p = memchr (p, '\n', (buf + bytes_read) - p)))

            {

              ++p;

              ++lines;

            }

          bytes += bytes_read;

        }

Quote:

Originally Posted by marozsas (Post 4237235)

may I suggest ...

Code:

cat -n /proc/net/ip_conntrack | tail -1 | awk '{print $1}'

"cat" is super fast and awk will receive just one line to output only the number....anyway, is just a crazy idea to test.

I tested it, but "wc -l" is much faster...

Code:

# time cat -n /test.pl | tail -n1

1933524 14467 addresses are on the whitelist

real    0m0.318s

user    0m0.240s

sys    0m0.040s

# time wc -l /test.pl

1933523 /test.pl



real    0m0.093s

user    0m0.076s

sys    0m0.016s

Quote:

Originally Posted by ntubski (Post 4237051)

Most of the time is in sys, which suggests that increasing the buffer size to reduce the number of calls to read(2) may help.

I think you're right.
But isn't there also room for speed improvement by just parsing the buffer in plain C (without calling a function in the C-library)?

The problem is that I can't put it into code...

Quote:

Originally Posted by frater (Post 4237842)

I think you're right.
But isn't there also room for speed improvement by just parsing the buffer in plain C (without calling a function in the C-library)?

If parsing time is 0.152s that's the room for speed improvement...

Quote:

The problem is that I can't put it into code...

Have you tried setvbuf? http://pastebin.com/vsyNNTrT

This is the standard wc -l

Code:

# time /usr/bin/wc -l /1.3GB.txt

32128160 /1.3GB.txt



real    0m49.020s

user    0m0.588s

sys    0m4.624s

I downloaded coreutils and compiled that wc, it turned out to be slightly faster than the one that came with Ubuntu 10.4LTS. I don't know why. It may even be due to the difference in version.

coreutils wc.c: http://pastebin.com/Z91ZFKrD

Code:

# time /opt/coreutil/coreutils-8.9/src/wc -l /1.3GB.txt

32128160 /1.3GB.txt



real    0m44.842s

user    0m1.120s

sys    0m1.584s

I modified the buffersize..

Code:

# diff wc.c wclb.c

54c54

< #define BUFFER_SIZE (16 * 1024)

---

> #define BUFFER_SIZE (1024 * 1024)

(your) lc compiled with -O3

Code:

# gcc lc.c -o lc -O3

# time ./lc /1.3GB.txt

32128160 /1.3GB.txt



real    0m47.802s

user    0m15.565s

sys    0m2.012s

# time ./lc /1.3GB.txt

32128160 /1.3GB.txt



real    0m45.938s

user    0m15.649s

sys    0m2.008s

(your) lc compiled with default options

Code:

# gcc lc.c -o lc

# time ./lc /1.3GB.txt

32128160 /1.3GB.txt



real    0m54.932s

user    0m19.857s

sys    0m1.864s

But you're using the library function 'getc' which is possibly a slow library function (according to that webpage). It may of course be a problem with the implementation on his machine....

In the old days when I was still writing in C for fast functions (in comparison with native Clipper) I never used any library functions. afaik this was not possible. There were some functions meant for parameter passing and allocating memory. I then parsed these buffers in native C. I posted these functions in public domain, but this was before Internet became popular. They were uploaded to my brother's BBS which was part of fidonet. I couldn't find any of my sources on the Internet...

Don't you think it's worthwile to change the source of coreutils wc.c instead of the other one which uses getc? wc.c uses another library function (memchr). This isn't needed is it? Or doesn't it give you a speed improvement?

Code:

      /* Use a separate loop when counting only lines or lines and bytes --

        but not chars or words.  */

      while ((bytes_read = safe_read (fd, buf, BUFFER_SIZE)) > 0)

        {

          char *p = buf;



          if (bytes_read == SAFE_READ_ERROR)

            {

              error (0, errno, "%s", file);

              ok = false;

              break;

            }



          while ((p = memchr (p, '\n', (buf + bytes_read) - p)))

            {

              ++p;

              ++lines;

            }

          bytes += bytes_read;

        }

    }

PS I googled my name in combination with Clipper and did find these files (how funny)

http://members.fortunecity.com/userg...tml/summer.htm
Trudf.zip
Set of MS C source UDFs (w/OBJs) that total numeric elements of an array, test null expressions, pad character strings, SOUNDEX(), & strip non-alphanumeric characters from strings - by J van Melis

That's more than 20 years ago.
I wish I could get hold of that file....

One idea is, use the size of the file 'stat -c %s' as long as the file has a constant number of characters per line ... other than that you cannot get any faster than wc -l.

Quote:

Originally Posted by H_TeXMeX_H (Post 4240474)

One idea is, use the size of the file 'stat -c %s' as long as the file has a constant number of characters per line ... other than that you cannot get any faster than wc -l.

You can't use that trick for /proc/sys/net/ip_conntrack
It's only a pseudo file and 'stat -c %s' returns 0 (as I found out a while ago in another situation)

But I already made progress by modifying the buffersize of "wc.c" (didn't you see the results I posted?)

I'm currently in the process of obtaining my 25 year old sources in C.
These sources don't contain calls to library functions.
Hopefully things will return and I may even pick up programming in C again.

I still think/hope there's some room for improvement.
I will keep you posted (also if I don't succeed)

Cheers and thanks for all the input,

JP

I saw the results, and I don't see huge improvement.

As for /proc/sys/net/ip_conntrack, I don't have the file, so I didn't know.

But then, how does wc -l work if the file has no size ?

Quote:

Originally Posted by H_TeXMeX_H (Post 4240838)

I saw the results, and I don't see huge improvement.

I'm looking for any improvement, but you are right.. not huge.
As I wrote in my original post. On a normal system this file contains about 600 lines.
There's no need for improvement then (0.01 second)

Code:

# time wc -l /proc/net/ip_conntrack

1498 /proc/net/ip_conntrack



real    0m0.009s

user    0m0.000s

sys    0m0.008s

But on that popular server we're talking about +/- 38000 lines which takes 10 seconds.
If I could bring this down to 6 seconds I'll be more happy than I am already.

This code is being used by a monitoring server which executes this every minute.
I don't want it to become an extra burden on such an already stressed system.

Quote:

Originally Posted by H_TeXMeX_H (Post 4240838)

As for /proc/sys/net/ip_conntrack, I don't have the file, so I didn't know.

Sorry, it's /proc/net/ip_conntrack
You will probably have it.

Quote:

Originally Posted by H_TeXMeX_H (Post 4240838)

But then, how does wc -l work if the file has no size ?

It works fine ;-)

BTW, today I got an email with those C-programs I wrote more than 25 years ago which I published later as shareware on fidonet. Just found them on the Internet.
http://pastebin.com/37UncgHf
This soundex function was done by Nantucket in assembly language using a complete different algorithm.
I wrote it in my own way in C (I found assembly too cumbersome) and made it 3 times as fast returning a 5 byte code instead of 4. Speed was a necessity because the function was used as an index key for a database.

Although I was an experienced programmer in Clipper, the only things I did in C were these little functions. All original work as I had no-one I could learn from (I didn't even know there was a thing called Internet). Later in my life I created some functions in 'C' managing sets (union, intersection...) (http://en.wikipedia.org/wiki/Set_%28mathematics%29).

You went and changed the benchmark! For 1.3GB.txt, it looks like most of the time is spent waiting for the disk since sys+user is much less than real time. I would suggest that you on test ip_conntrack since that is what you are actually interested in.

Quote:

Originally Posted by ntubski (Post 4241745)

I would never have done this if I had a choice in this. I have no access to that server nor will I ever have.
I don't have any server at my disposal that handles that many connections.

I tried writing a script to open 40000 connections but I found things slowed to a crawl around 15000. I'll give it another shot on the weekend.

I also found conntrack while searching:

Quote:

conntrack provides a full featured userspace interface to the netfilter connection tracking system that is intended to replace the old /proc/net/ip_conntrack interface.

Might be a faster method of listing connections if you have it installed on your server.

So it turns out increasing the buffer size doesn't help, I rewrote lc.c to use open() and read(), and discovered that it doesn't read() more than 4096 bytes at a time.

Code:

~/tmp$ ./lc /proc/net/ip_conntrack

nread = 4080, BUFFER_SIZE = 4194304

nread = 4080, BUFFER_SIZE = 4194304

nread = 4080, BUFFER_SIZE = 4194304

nread = 3060, BUFFER_SIZE = 4194304

    76 /proc/net/ip_conntrack

Code:

/* Sample implementation of wc utility. */



#include <string.h>

#include <unistd.h>

#include <stdlib.h>

#include <stdio.h>

#include <stdarg.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>







typedef unsigned long count_t;  /* Counter type */



static char *buffer;

/* make this a bit bigger than the size of the file */

#define BUFFER_SIZE (4*1024*1024) /* 3 891 335 */



/* Current file counters: chars, words, lines */

count_t ccount;

count_t wcount;

count_t lcount;



/* Totals counters: chars, words, lines */

count_t total_ccount = 0;

count_t total_wcount = 0;

count_t total_lcount = 0;



/* Print error message and exit with error status. If PERR is not 0,

  display current errno status. */

static void

error_print (int perr, char *fmt, va_list ap)

{

    vfprintf (stderr, fmt, ap);

    if (perr)

        perror (" ");

    else

        fprintf (stderr, "\n");

    exit (1);

}



/* Print error message and exit with error status. */

static void

errf (char *fmt, ...)

{

    va_list ap;



    va_start (ap, fmt);

    error_print (0, fmt, ap);

    va_end (ap);

}



/* Print error message followed by errno status and exit

  with error code. */

static void

perrf (char *fmt, ...)

{

    va_list ap;



    va_start (ap, fmt);

    error_print (1, fmt, ap);

    va_end (ap);

}



/* Output counters for given file */

void

report (const char *file, count_t lcount)

{

    printf ("%6lu %s\n", lcount, file);

}



/* Process file FILE. */

void

counter (const char *file)

{

    int fd = open (file, O_RDONLY);

    int total_read = 0, lcount = 0;



    if (fd < 0)

        perrf ("cannot open file `%s'", file);



    for (;;) {

        int nread = read(fd, buffer+total_read, BUFFER_SIZE - total_read);

        if (nread < 0) perrf("read");

        if (nread == 0) break;  /* eof */

        total_read += nread;

        /* printf("nread = %d, BUFFER_SIZE = %d\n", nread, BUFFER_SIZE); */

    }



    for (const char *p = buffer; p; p = memchr(p+1, '\n', total_read - (p+1 - buffer)))

        lcount++;



    report (file, lcount);

    total_lcount += lcount;



    close(fd);

}



int

main (int argc, char **argv)

{

    int i;



    if (argc < 2)

        errf ("usage: lc FILE [FILE...]");



    buffer = malloc(BUFFER_SIZE);



    for (i = 1; i < argc; i++)

        counter (argv[i]);



    if (argc > 2)

        report ("total", total_lcount);

    return 0;

}

The program to open a bunch of ports, if anyone is interested:

Code:

#include <assert.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <sys/types.h>

#include <sys/socket.h>

#include <netdb.h>

#include <unistd.h>

#include <netinet/in.h>

#include <sys/epoll.h>



int client_socket(int port)

{

    int status, yes = 1, fail;

    struct addrinfo hints;

    struct addrinfo *servinfo, *si;  // will point to the results

    char portname[8];

    int sockfd;



    snprintf(portname, sizeof portname, "%d", port);



    memset(&hints, 0, sizeof hints); // make sure the struct is empty

    hints.ai_family = AF_INET;

    hints.ai_socktype = SOCK_STREAM; // TCP stream sockets

    hints.ai_flags = AI_NUMERICSERV; /* numeric address */



    if ((status = getaddrinfo("127.0.0.1", portname, &hints, &servinfo)) != 0) {

        fprintf(stderr, "getaddrinfo error: %s\n", gai_strerror(status));

        exit(1);

    }



    // servinfo now points to a linked list of 1 or more struct addrinfos

    for (si = servinfo; si; si = si->ai_next) {

        sockfd = socket(si->ai_family, si->ai_socktype, si->ai_protocol);

        if (sockfd < 0) {

            perror("socket");

            continue;

        }



        fail = setsockopt(sockfd, SOL_SOCKET, SO_REUSEADDR, &yes, sizeof yes);

        if (fail) { perror("fail"); exit(1); }



        break;

    }



    if (!si) {

        exit(1);

    }

    freeaddrinfo(servinfo); // free the linked-list



    fail = connect(sockfd, si->ai_addr, si->ai_addrlen);

    if (fail) { perror("connect"); exit(1); }

    return sockfd;

}



int server_socket(int port)

{

    int status, yes = 1, fail;

    struct addrinfo hints;

    struct addrinfo *servinfo, *si;  // will point to the results

    char portname[8];

    int sockfd;



    snprintf(portname, sizeof portname, "%d", port);



    memset(&hints, 0, sizeof hints); // make sure the struct is empty

    hints.ai_family = AF_INET;

    hints.ai_socktype = SOCK_STREAM; // TCP stream sockets

    hints.ai_flags = AI_PASSIVE;    // fill in my IP for me



    if ((status = getaddrinfo(NULL, portname, &hints, &servinfo)) != 0) {

        fprintf(stderr, "getaddrinfo error: %s\n", gai_strerror(status));

        exit(1);

    }



    // servinfo now points to a linked list of 1 or more struct addrinfos

    for (si = servinfo; si; si = si->ai_next) {

        sockfd = socket(si->ai_family, si->ai_socktype, si->ai_protocol);

        if (sockfd < 0) continue;



        fail = setsockopt(sockfd, SOL_SOCKET, SO_REUSEADDR, &yes, sizeof yes);

        if (fail) { perror("fail"); exit(1); }

        fail = bind(sockfd, si->ai_addr, si->ai_addrlen);

        if (!fail) break;

        else close(sockfd);

    }



    if (!si) {

        perror("bind");

        exit(1);

    }

    freeaddrinfo(servinfo); // free the linked-list



    fail = listen(sockfd, 1);

    if (fail) {

        perror("listen");

        exit(1);

    }



    return sockfd;

}



int main(int argc, char **argv)

{

    assert(argc == 4);

    int portlo = atoi(argv[2]);

    int porthi = atoi(argv[3]);

    assert(portlo && porthi);



    if (strcmp("--client", argv[1]) == 0) {

        for (int p = portlo; p < porthi; p++) {

            client_socket(p);

            if (p % 100 == 0) printf(".");

            if (p % 1000 == 0) printf("%d\n", p);

        }

        goto hang;

    } /* else serve */



    int epollfd;

#define MAX_EVENTS 1024

    static struct epoll_event ev, events[MAX_EVENTS];



    epollfd = epoll_create(porthi - portlo);

    if (epollfd < 0) { perror("epoll_create"); exit(1); }



    ev.events = EPOLLIN;

    for (int p = portlo; p < porthi; p++) {

        int sock = server_socket(p);

        ev.data.fd = sock;

        if (epoll_ctl(epollfd, EPOLL_CTL_ADD, sock, &ev) == -1) {

            perror("epoll_ctl(add, listener)");

            exit(1);

        }

        if (p % 100 == 0) printf(".");

        if (p % 1000 == 0) printf("%d\n", p);

    }



    for (;;) {

        int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);

        if (nfds < 0) { perror("epoll_wait"); exit(1); }

        for (int n = 0; n < nfds; n++ ) {

            int tcpsock = accept(events[n].data.fd, NULL, NULL);

            if (tcpsock < 0) {

                perror("accept"); exit(1);

            }

            if (epoll_ctl(epollfd, EPOLL_CTL_DEL, events[n].data.fd, &events[n]) == -1) {

                perror("epoll_ctl(del, listener)"); exit(1);

            }

            close(events[n].data.fd); /* done listening */

        }

    }



 hang:

    for (;;) sleep(1);

    return 0;

}