core: make clist singly-linked by kaspar030 · Pull Request #4923 · RIOT-OS/RIOT

kaspar030 · 2016-02-29T00:46:01Z

clist was doubly linked in order to enable removal of threads from a run queue in constant time.

Today I realized that only the currently running thread can remove itself from a running queue (by blocking for a msg, mutex, sleeping, ...), and a singly linked but circular list offers O(1) removal of the head element.
So I changed clist accordingly.

This carves off 4 byte of tcb and increases context switch ~~time~~ performance by ~4%.

~~Waiting for #4557.~~

OlegHahm · 2016-02-29T07:10:32Z

Nice!

haukepetersen · 2016-02-29T10:13:01Z

I like!

miri64 · 2016-02-29T11:47:22Z

tests/unittests/tests-core/tests-core-clist.c

 #define TEST_CLIST_LEN    (8)

-static clist_node_t tests_clist_buf[TEST_CLIST_LEN];
+static list_node_t tests_clist_buf[TEST_CLIST_LEN];


Here and below: the datatype is called list now so the variable, function and file names should reflect that.

Even if clist_*() works with list_node_t objects?

But doesn't clist stand for circular list? (or is it that still)?

Yes. I shared the list node definition between the two header files. Now I copied the definition, do you prefer it that way?

Why copy when you can

typedef list_t clist_t;

typedef'ed it is now.

kaspar030 · 2016-03-12T00:45:51Z

rebased
made clist.h independent from list.h

miri64 · 2016-03-12T15:28:35Z

Why does this depend on #4557? This data structure should be independent of that change, right?

kaspar030 · 2016-03-12T15:47:20Z

Why does this depend on #4557? This data structure should be independent of that change, right?

#4557 introduces link.h. With copying the struct, this PR was independent. With the typedef, it's not.

miri64 · 2016-03-12T15:48:29Z

Why can't you take the list.h introduction over here and make #4557 dependent on this PR. That seems to be the more logical dependency graph to me.

kaspar030 · 2016-03-12T15:51:59Z

The perfect graph would be a "list.h" introduction PR, and then #4557 and this. Moving the list.h introduction here just shuffles the imperfect graph solution here.

I'd prefer merging #4557, then merging this.

OlegHahm · 2016-03-28T10:33:12Z

Dependency not yet merged. Postponed.

kaspar030 · 2016-03-28T10:46:29Z

Sad.

OlegHahm · 2016-03-28T10:50:24Z

Agreed, but currently I don't see realistic chances for #4557 to get merged until tomorrow. Do you disagree?

kaspar030 · 2016-03-28T10:56:54Z

Can't review it myself...

OlegHahm · 2016-03-28T11:02:30Z

You can kick your reviewers. ;)

haukepetersen · 2016-03-29T19:55:06Z

core/include/clist.h

+ *
+ * Each list is represented as a "clist_node_t". It's only member, the "next"
+ * pointer, points to the last entry in the list, whose "next" pointer points to
+ * the first entry.


Something reads weird here, how about

... . It's only member, the "next" pointer, points to the next entry in the list. The last element's "next" pointer points to the first entry.

missread the sentence, never mind...

miri64 · 2016-03-29T20:24:02Z

Needs rebase.

kaspar030 · 2016-03-29T20:35:25Z

rebased, squashed

haukepetersen · 2016-03-29T20:39:38Z

Code looks good, works as expected (on 'native' and some ARM boards), code size is smaller than before -> ACK!

cgundogan · 2016-03-29T21:27:49Z

code looks sensible and changes make sense. ACK

kaspar030 added Type: enhancement The issue suggests enhanceable parts / The PR enhances parts of the codebase / documentation Area: core Area: RIOT kernel. Handle PRs marked with this with care! labels Feb 29, 2016

kaspar030 assigned OlegHahm Feb 29, 2016

kaspar030 added the State: waiting for other PR State: The PR requires another PR to be merged first label Feb 29, 2016

kaspar030 mentioned this pull request Feb 29, 2016

core: reduce types of tcb->status and tcb->priority #4924

Merged

miri64 reviewed Feb 29, 2016
View reviewed changes

kaspar030 force-pushed the optimize_clist branch from 6a376dd to 62504f3 Compare March 12, 2016 00:44

kaspar030 added this to the Release 2016.04 milestone Mar 21, 2016

OlegHahm modified the milestones: Release 2016.07, Release 2016.04 Mar 28, 2016

kaspar030 force-pushed the optimize_clist branch from cf058ed to b308448 Compare March 29, 2016 17:31

haukepetersen reviewed Mar 29, 2016
View reviewed changes

kaspar030 force-pushed the optimize_clist branch from b308448 to 0415ff9 Compare March 29, 2016 20:32

kaspar030 removed the State: waiting for other PR State: The PR requires another PR to be merged first label Mar 29, 2016

haukepetersen added the CI: ready for build If set, CI server will compile all applications for all available boards for the labeled PR label Mar 29, 2016

kaspar030 modified the milestones: Release 2016.04, Release 2016.07 Mar 29, 2016

kaspar030 added 2 commits March 30, 2016 00:27

core: clist: make singly linked

f9f6adb

tests: unittests: adapt tests-core-clist to singly linked clist

1bac3f3

kaspar030 force-pushed the optimize_clist branch from 0415ff9 to 1bac3f3 Compare March 29, 2016 22:27

OlegHahm merged commit 07b1c94 into RIOT-OS:master Mar 29, 2016

OlegHahm mentioned this pull request Mar 29, 2016

core: add thread flags #4103

Merged

kaspar030 deleted the optimize_clist branch February 7, 2017 22:13

Conversation

kaspar030 commented Feb 29, 2016

Uh oh!

OlegHahm commented Feb 29, 2016

Uh oh!

haukepetersen commented Feb 29, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kaspar030 commented Mar 12, 2016

Uh oh!

miri64 commented Mar 12, 2016

Uh oh!

kaspar030 commented Mar 12, 2016

Uh oh!

miri64 commented Mar 12, 2016

Uh oh!

kaspar030 commented Mar 12, 2016

Uh oh!

OlegHahm commented Mar 28, 2016

Uh oh!

kaspar030 commented Mar 28, 2016

Uh oh!

OlegHahm commented Mar 28, 2016

Uh oh!

kaspar030 commented Mar 28, 2016

Uh oh!

OlegHahm commented Mar 28, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

miri64 commented Mar 29, 2016

Uh oh!

kaspar030 commented Mar 29, 2016

Uh oh!

haukepetersen commented Mar 29, 2016

Uh oh!

cgundogan commented Mar 29, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants